Teoria da compu

Trabalho 01 de teoria da computação
1. O que é alfabeto? É um conjunto finito de simbolos

2. Defina o conceito de cadeia. É uma sequencia finita de simbolos de um alfabeto

3. Defina o conceito de linguagem e mostre um exemplo. É um conjunto de palavras de um alfabeto

Exemplo: Assim, L = {0, 1, 00, 01, 10, 11} seria um exemplo de linguagem formada a partir do alfabeto ∑ = {0, 1}. A quantidade de cadeias pertence à uma linguagem não é necessariamente finita.
4. O que é fechamento de um alfabeto?

Resposta: Fechamento de um alfabeto é o conjunto de todas as cadeias possíveis de se formar a partir dos símbolos deste alfabeto. Denota-se o fechamento de um alfabeto ∑ por ∑*. Para o alfabeto ∑ = {1} por exemplo, ∑* seria formado por todas as seqüências possíveis do símbolo “1”, de qualquer tamanho. Pode-se notar que, basta que o alfabeto possua um único símbolo (conjunto não vazio) para que o seu fechamento seja infinito.
5. Como se pode descrever uma linguagem formal?

Resposta: Uma linguagem formal pode ser descrita por um modelo reconhecedor ou por um modelo gerador. Um modelo reconhecedor é um modelo matemático capaz de percorrer (“varrer”) uma cadeia de símbolos construída a partir de um alfabeto e, ao final desta “varredura”,identificar se esta cadeia faz parte
6. Descreva sobre as aplicações de LFA (Linguagens Formais e Autômatos).

Resposta: Se x é prefixo de y, então y = xz, com x, y e z *;
Se y é prefixo de x, então x = yu, com x, y e u *;
Se y = xz e x = yu, então (por substituição) podemos dizer que x = xzu;
Se x = xzu, então podemos dizer que zu = , pois é o elemento neutro da operação de concatenação;
Se zu = , então podemos dizer que z = e u = ;
Assim, tomando a afirmação inicial y = xz, temos que y = x= x. Ou seja, y = x sempre que y for prefixo de x e x for prefixo de y ao mesmo tempo

7. Defina o conceito de subpalavra.

Resposta:

Dadas x e y, cadeias pertencentes à *. Uma