Teoria Da Computação

Dada a tabela de transição do autômato finito não determinístico represente o autômato:

9. Considere a linguagem: L=(w|w possui como sufixo a ou bb ou cc} e transcreva sua tabela de transição.

10. Descreva o autômato a partir do traço de execução:: Teoria da Computação Professora: Adriana Andrade E-mail: [e-mail]

Aula 08- Revisão para prova

1.Seja a palavra teoria determine:

a)Prefixo:

b)Sufixo:

2.Suponha o alfabeto ∑ {a,b} e as palavras v=baa e w=bb, tem-se que:

a)vw=

b)vε=

c)wv=

3. Se abcb é uma palavra sobre o alfabeto {a, b, c}, então defina:

a)*

b)+

c)|abbc|

d)|ε|

4. Derive três sentenças da gramática abaixo, onde G = ({Vn,Vt,P,S}, Vn{X,Y,Z}, Vt={1,0,+,*}, P, S=X): P = { X → X+Y X → Y Y→ Y*Z Y→ Z Z→ 1 Z→ O }

5 Derive o número 145 através da gramática G =({Vn,Vt,P,S}, onde: Vn {S,D}, Vt {0,1,2, ..., 9},P,S): P = { S→D

S →DS,

D → 0|1|2| ... |9 }

6. Seja Σ={0,1,2,3,4,5,6,7,8,9}, construa AFD para a seguinte linguagem

{x Σ+ | a sequência descrita por x corresponde a um valor divisível por 2}

7. A partir AF abaixo, descreva as tabelas de transições e apresente pelo menos três palavras formadas por cada autômato e classifique os autômatos em AFN ou AFD.

. O modelo matemático de uma máquina de estados finitos é conhecido como:

a)Computabilidade.

b)Algoritmo.

c)Alfabeto.

d)Autômato.

e)Linguagem.

12. Na Linguagem Formal pode-se afirmar que:

I. Alfabeto é o conjunto finito de símbolos e ou caracteres que definem uma determinada linguagem.

II. Palavra é uma cadeia de símbolos sobre um determinado alfabeto que definem atributos e significados de uma determinada linguagem.

III. Concatenação é a associação de uma palavra a outra e definem atributos e significados de uma determinada linguagem.

Assinale a alternativa correta.

a)Todas as afirmações estão corretas.

b)Todas as afirmações estão incorretas.

c)Somente a afirmação I está correta.

d)Somente a afirmação II está correta.

e)Somente a afirmação III está correta.

13.Em relação aos autômatos