FTC 15/03/2011

Professor Newton Vieira

Primeira Prova: 07/04

Bibliografia: Introdução aos Fundamentos da Computação - Newton Vieira

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Conceitos Iniciais:

-->Definindo ALFABETO:
    Um Alfabeto é um conjunto de simbolos, sendo estes qualquer rabisco que voce possa imaginar e quiser chamar de simbolo.
    Necessariamente um Alfabeto deve conter ao menos 1 simbolo, não existindo um Alfabeto vazio.

- Notações para um ALFABETO:
  {simbolo1,simbolo2,simbolo3} cita simbolo a simbolo todo o conteúdo de um Alfabeto.

-->Definindo PALAVRA:
    Uma palavra é uma sequencia finita de simbolos quaisquer de um Alfabeto.
    Uma notação importante usada em palavras é o simbolo vazio denotado por <lambida>, que não pertence a nem um Alfabeto pois não ao invez de denotar um simbolo, denota a ausencia de um simbolo.

    Nota: Um exemplo usado frequentemente pelo professor para "Palavra" é o código do inicio ao fim de um programa em C por exemplo, incluindo espaços em branco, pontos, virgulas e quebras de linha, sendo todos simbolos pertencentes a palavra. Esse conceito de Palavra portanto se diferencia um pouco do sentido usual, e não necessariamente é uma sequencia pequena de letras.

- Notações para PALAVRA:
  abcd é uma palavra com 4 simbolos.
  <lambida> também é uma palavra, porem ela não contem nem um simbolo.

-->Definindo LINGUAGEM:
    Uma Linguagem é um conjunto de Palavras, com a restrição de que estas Palavras sejam, juntas, um sub-conjunto do total de Palavras que podem ser geradas a partir dos simbolos de um Alfabeto.
    (obs: a notação para o conjunto de todas as palavras de um alfabeto de nome "alfa" é "alfa*").
    Um detalhe sobre os tipos de Linguagens que existem é que como o conjunto vazio também é um conjunto ele se enquadra na definição de Linguagem. Outro detalhe importante que facilmente nos esquecemos é de que apesar de a palavra <lambida> é a ausencia de simbolos, não podendo portanto ser confundida com a ausencia de palavras. Ou seja uma Linguagem vazia não possui a palavra <lambida> e não obstante uma Linguagem não vazia também pode existir sem a presença dessa palavra especifica.

    Nota: Existem Linguagens finitas, mas as mais utilizadas por sua praticidade são as infinitas.

- Notações para LINGUAGEM:
  Ja que uma Linguagem pode vir a ser finita ou não, pode-se expressa-la citando elemento por elemento da mesma ou expressando a regra pela qual as palavras dessa linguagem se formam.
  {palavra1,palavra2,palavra3} é um modo de expressar uma Linguagem elemento a elemento.
    Um exemplo pratico do dito acima: {a, ab, abc} indicando uma linguagem com 3 palavras: "a", "ab", "abc".
  { Caracteristica da Linguagem | Restrições da Linguagem } que expressa as regras de construção que delimitam as palavras.
    Um exemplo pratico do dito acima: {palavra € NATURAIS | o numero de zeros é impar} indicando uma palavra composta pelos numeros naturais com numero de zeros impar.


    Notas: Pode-se usar operadores de conjuntos sobre linguagens, a exemplo L1 U L2, L1-L2, intercessão e complemento.

    O conjunto potencia de uma linguagem é o conjunto de todos os subconjuntos daquela linguagem.
    E pode ser expresso assim: P(L1) -> sendo isso entendido como um conjunto de linguagens.
    Vale lembrar que um conjunto potencia de uma Linguagem não é uma Linguagem mas sim um conjunto de Linguagens.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

-->Operações sobre Alfabetos:

 - Fecho de Kleene:
    "Alfa*" ou {a,b,c}* é o conjunto de todas as palavras formadas pelos simbolos dos alfabetos relacionados.
    Observe que o conjunto gerado por este operador ("Alfa*") é infinito, pois mesmo o menor dos alfabetos tem, ao menos, 1 simbolo, o que gera infinitas palavras formadas por concatenações do mesmo. ex: a, aa, aaa, aaa...a, etc.
    Outro detalhe a se chamar a atenção é para o fato de que o resultado dessa notação "alfa*" é uma Linguagem.
    Também vale citar que a mesma notação também opera sobre Linguagens, gerando também uma Linguagem.
    A definição do Fecho de Kleene será feita novamente no contexto de Linguagens na sessão de Operações sobre Linguagens.

- Exemplos comuns do uso das notações acima:
  { palavra € {0,1}* | numero de zeros é impar } indica uma Linguagem formada por 0`s e 1`s com numero impar de zeros.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Operações e conceitos sobre Palavras:

|palavra| é uma notação que se refere ao comprimento da palavra, no caso |palavra| corresponde ao comprimento 7.

A notação para se concatenar duas palavras é colocas em sequencia ex: pL1pL2 é a concatenação de pL1 e pL2.

O operador de reverso que indica a mesma palavra escrita de tras para frente é um " elevado a R " ou seja (abc)^R é cba

Sub-palavra: Z é sub-palavra de W se xZy = W, sendo x e y palavras quaisquer. Ou seja Z esta contido em W.

O conceito de x ser prefixo de w significa que x é uma sub-palavra de w iniciada na ponta esquerda.

Sufixo é o mesmo conceito invertido.

Se desejar calcular o numero máximo de subpalavras que pode existir em uma palavra a equação é: ((n/2)) + 1.

"a³" é um operador sobre a palavra "a" que indica, no contexto dessa materia, a repetição do simbolo pelo numero de vezes indicado pelo valor numerico, portanto "a³" indica a palavra "aaa" e a^n indica aaaa...a n vezes.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Operações e Notações sobre Linguagens:

A concatenação de duas linguagens L1 e L2 é uma terceira linguagem cujas palavras são formadas por cada uma das palavras de L1 concatenadas com cada uma das palavras de L2 uma a uma.
Ou seja se L1 = {a,b,c} e L2 = {0,1}, L1L2 = {a0,a1,b0,b1,c0,c1}
ou mudando um pouco a notação: {a,b,c}{0,1} = {a0,a1,b0,b1,c0,c1}.

// O professor fez uma analogia da descrição acima com um produto cartesiano de 2 conjuntos, com a diferença que no produto cartesiano de duas linguagens não se obtem uma terceira linguagem mas sim um conjunto de de conjuntos.
// Essa observação acima é bem pouco importante e desnecessária, não se deixe confundir por ela.

Repare que uma concatenação de L1 com a linguagem Conjunto Vazio geraria um Conjunto Vazio como resultado pois não haveria nenhum caso em que houvesse duas palavras para serem concatenadas, já não há nem uma palavra no Conjunto Vazio.
Repare também que é possivel concatenar uma palavra qualquer a palavra <lambida> portando: {<lambida>,a}{0,1} = {0,1,a0,a1}

A notação para expressar N concatenações da mesma linguagem em sequencia é Linguagem^N sendo N o numero de repetições assim como é feito na concatenação entre palavras.
É convenção dizer que Linguagem^0 é {<lambida>}
Essa convenção é surgida da ideia de que L^N = L^(N-1) concatenado com L e portanto L^1 = L^0L e o unico jeito disso ser verdade é se L^0 for {<lambida>}.
Essa convenção vale mesmo em Linguagens como esta: {aa,bb} que claramente não possui a palavra <lambida>, mas elevada a 0 sera {<lambida>}.

// A seguir somos introduzidos ao fecho de Kleene pela segunda vez:
A notação L* (asterisco) é chamada de fecho de kleene e indica todas as concatenações das palavras de L com outras palavras dele mesmo repetidamente infinitas vezes. ou seja seria L união LL união com LLL união com LLL...L etc. Ou seja tudo que voce conseguir formar misturando as palavras de L umas com as outras.

Uma outra notação semelhante que é denotada por L+ é o fecho positivo de kleene que é a mesma coisa do L* mas sem a inclusão de L^0 no inicio da concatenação.

Mas tenha cuidado nesse ponto pois há uma confusão que se gera com o L+. Observe os exemplos abaixo para entender:

{aa, bb}* = {<lambida>, aa, bb, aaaa, aabb, bbbb, bbaa, ... etc etc}
{aa, bb}+ = {aa, bb, aaaa, aabb, bbbb, bbaa, ... etc etc}

POREM:
{<lambida>, aa, bb}* = {<lambida>, aa, bb, aaaa, aabb, bbbb, bbaa, ... etc etc}
{<lambida>, aa, bb}+ = {<lambida>, aa, bb, aaaa, aabb, bbbb, bbaa, ... etc etc}

sendo portando {<lambida>, aa, bb}* = {<lambida>, aa, bb}+ quando a Linguagem ja possuir a palavra Lambida sem ser elevada a 0.