O Exercício de Autômatos

Lista de Exercícios 3

1. Mostre três cadeias de tamanho maior ou igual a quatro que podem ser geradas pela

gramática livre de contexto abaixo:

G1 = ({S,J,P,D,E}, {1,2,.}, P1, S),

onde P1 é o conjunto de produções:

[pic 1]

1. Diga se a gramática livre de contexto G2 gera as cadeias abaixo. Construa uma de- rivação e uma árvore de derivação para as cadeias que a gramática puder gerar.

G2 = ({S,T}, {a,b}, P2, S),

onde P2 é o conjunto de produções:

[pic 2]

1. ε
2. aba
3. baa
4. abba
5. aabb

---

1. Uma gramática é dita ambígua sse (se e somente se) for possível criar duas árvores de derivação para uma mesma cadeia terminal. Prove que a gramática livre de con- texto G4 definida abaixo1 é uma gramática ambígua. ().

[pic 3]

1. Na gramática livre de contexto abaixo, considere que os não-terminais são os nomes entre os símbolos “<” e “>” e que, nas produções, ao invés da seta (→), são usados a seqüência de símbolos: dois-pointos, dois-pontos, igual (::=). Essa é a formatação conhecida como notação BNF. Com base na gramática abaixo G6, dada nessa no- tação, resolva as questões:

[pic 4]

1. Dê um exemplo de derivação de uma cadeia na gramática acima que use ao menos um .
2. Mostre uma árvore de derivação para a cadeia.
3. Prove que a gramática acima é ambígua.

[pic 5]

1 A partir de agora daremos apenas as produções da gramática. Em geral, as letras maiúsculas serão não- terminais e o não-terminal no lado esquerdo (cabeça) da primeira produção será o não-terminal de início.

---

1. Abaixo, mostramos um exemplo de AP não-determinístico para reconhecer palavras na forma w.wr, ou seja, palavras cuja segunda metade (wr) é o reverso da primeira metade (w). Para cada cadeia abaixo, encontre alguma computação que comprove que ela é aceita pelo autômato.

[pic 6]

1. aa
2. abba
3. bbbb

1. O Autômato com Pilha abaixo reconhece as cadeias sobre o alfabeto {a, b} que têm a mesma quantidade de a’s e de b’s. Mostre, nesse autômato, uma computação de aceitação para cada uma das cadeias dadas (todas são aceitas):

[pic 7]

1. ba
2. aabb
3. baba
4. bbabaa

1. Converta as gramáticas das questões 2 e 3 para Autômatos com Pilha equivalentes.

1. Considerando que a Máquina de Turing dada a seguir tem {a,b,c} como alfabeto de entrada e que usa L para representar “esquerda” (left) e R para representar “di- reita” (right), resolva as questões:

1. Mostre a computação da cadeia “aabc”. Diga se a cadeia é ou não reconhe- cida e justifique.
2. Mostre a computação da cadeia “aabbcc”. Diga se a cadeia é ou não reco- nhecida e justifique.
3. Cite um exemplo de cadeia reconhecida e um exemplo de cadeia não reco- nhecida pela MT dada. (Não pode citar as cadeias anteriores).

---

1. Descreva informalmente a linguagem que ela reconhece.

[pic 8]

1. Considerando a Máquina de Turing abaixo, que tem {a,b} como alfabeto de en- trada, responda:

1. Mostre o estado e a fita a cada passo do processo de reconhecimento da ca- deia “bab”. Ao final, diga se a palavra é ou não reconhecida e justifique.
2. Dê dois exemplos de cadeias da linguagem dessa MT e dois exemplos de ca- deias que não são da linguagem dessa MT.

[pic 9]

1. Sobre os diferentes modelos computacionais que estudamos, responda:

---

1. Quais os nomes dos modelos.
2. Qual o mais poderoso dos modelos? Como são chamadas as linguagens que podem ser representadas com esse modelo?
3. Qual o menos poderoso? Como são chamadas as linguagens que podem ser representadas com esse modelo?

1. O que é um problema de decisão? O que esse tipo de problema tem a ver com o conceito formal de linguagens?

1. Quando um problema de decisão é classificado como decidível?

1. Prove que é decidível o problema de testar se um número representado na forma decimal (dígitos de 0 a 9) é par. Prove isso de maneira clara, construindo uma Má- quina de Turing.

1. Crie uma gramática livre de contexto em notação BNF para gerar uma seqüência de expressões numéricas separadas por ponto-e-vírgula. Considere que os números da expressão tenham um só dígito de 0 a 9. As operações permitidas serão apenas adição (+) e multiplicação (*). Exemplos de cadeias que a sua gramática deve gerar são: “3”, “1+2*3;7+9”, “2+1;3;4+3+2;2;5*1”.

1. Construa uma gramática livre de contexto, usando a notação BNF, para especificar a sintaxe da linguagem de programação descrita informalmente abaixo:

1. Um programa é composto de um ou mais procedimentos.
2. Cada procedimento é definido assim:

• Inicia com a palavra “proc”
• Depois vem um identificador
• Depois vem um bloco

1. Um identificador pode ser qualquer palavra formada apenas por letras

(uma ou mais).

1. Assuma que as letras podem ir apenas de ‘a’ a ‘d’.
2. Um bloco

• Inicia com “[[“
• Depois vem uma seqüência de comandos, possivelmente vazia
• Termina com “]]”

1. Um comando é definido assim:

• Ou a palavra “var” seguida de um identificador seguido de “;” (representa uma declaração de variável).
• Ou um identificador seguido de “<-” seguido de uma expres- são seguida de “;” (representa uma atribuição).
• Ou um identificador seguido da cadeia “();” (representa uma chamada de procedimento).

1. Uma expressão é definida assim:

• Uma expressão seguida de “*” seguida de outra expressão.

---

• Ou “-“ seguido de uma expressão
• Ou simplesmente a cadeia “41”.
• Ou simplesmente um identificador.

1. Dê um exemplo de cadeia que possa ser gerada pela gramática que você deu como resposta para a questão anterior. A cadeia deve usar ao menos um comando. Mostre também uma árvore de derivação para a cadeia.

1. Dê uma explicação razoável (um esboço de uma prova matemática) para justificar que os seguintes problemas são decidíveis:

1. Testar se um dado AFD M aceita a cadeia vazia.
2. Testar se um dado AFN M aceita a cadeia vazia.
3. Testar se um dado AFD M aceita uma cadeia qualquer w.
4. Testar se uma dada expressão regular R gera uma cadeia dada w.
5. Testar se um dado AFD M representa a linguagem vazia (ou seja, testar se M

não aceita nenhuma cadeia).

1. Testar se uma dada GLC G representa a linguagem vazia (ou seja, testar se G

não gera nenhuma cadeia).

...