Expressões regulares

1. Que linguagem as expressões abaixo representam?

• 00
• (0 + 1)*
• (0 + 1) * 00(0 + 1)*
• a + b * c
• 0 * 1 * 2*
• 01 *  + 10*

2. Escreva uma expressão regular para as linguagens definidas abaixo:

• O conjunto de cadeias sobre 0, 1 que termine com três 1’s consecutivos.
• O conjunto de cadeias sobre 0, 1 que tenha ao menos um 1.
• O conjunto de cadeias sobre 0, 1 que tenha no máximo um 1

Autômatos

1. A seguir estão os diagramas de estado de dois AFDs, M₁ e M₂. Responda às seguintes questões sobre cada uma dessas máquinas.

• Qual é o estado inicial?
• Qual é o conjunto de estados de aceitação?
• Por qual sequência de estados a máquina passa para a entrada aabb?
• A máquina aceita a cadeia aabb?
• A máquina aceita a cadeia ϵ?
• Faça a tabela de transição dos dois autômato.

2. Dê a descrição formal das Máquinas M₁ e M₂ desenhadas no Exercício anterior.

3. Explique os elementos que definem a 5-upla de um:

• autômato finito determinístico
• autômato finito não-determinístico

4. Diferencie Autômato Finito determinístico de não-determinístico e de pilha

5. Explique qual é a linguagem definida pela expressão regular (0 + 1) * 1(0 + 1) e faça um autômato finito que reconheça esta linguagem

• É possível fazer um autômato finito determinístico?

6. Faça um autômato que reconheça as linguagens:

• {aⁱb^jc^k|i, j, k ∈ N, i + k = j}
• {aⁿb^m|n ≤ m ≤ 2n}
• {aⁱb^jc^k|i, j, k ≥ 0 e i = j ou i = k}

7. Explique os elementos que formam a 6-upla de um autômato de pilha

8. Diferencie autômato de pilha com autômato finito não-determinístico

9. Faça um autômato de pilha que reconheça a linguagem { w w^R | w {0,1}* }$

• Considere que w^R é o inverso de w, por exemplo: 0110

GLC

1. Defina o conceito de GLC ( e o que significa este acrônimo?)

2. Defina os elementos que formam a 4-upla de uma gramática livre do contexto.

3. Dada a GLC abaixo:

E -> E + T | T
T -> T x F | F
F -> (E) | a

Dê árvores sintáticas e derivações para cada cadeia abaixo.

• a
• a + a
• a + a + a
• ((a))

4. Responda cada item para a seguinte gramática livre-do-contexto G

R -> XRX | S
S -> aTb | bTa
T -> XTX | X | \epsilon
X -> a | b

• Quais são as variáveis de G?
• Quais são os terminais de G?
• Qual é a variável inicial de G?
• Verdadeiro ou falso? T -> aba
• Verdadeiro ou falso? T -> T
• Dê três cadeias de L(G)
• Dê três cadeias que não estão em L(G)
• Dê uma descrição em português de L(G)

5. Seja G = (V, Σ, R,  < STMT > ) a seguinte gramática

<STMT> -> <ASSIGN> | <IF-THEN> | <IF-THEN-ELSE>
<IF-THEN> -> if condition then <STMT>
<IF-THEN-ELSE> -> if condition then <STMT> else <STMT>
<ASSIGN> -> a:=1

• Liste quais são os elementos em V e em Σ?
• Mostre que G é ambígua

6. Resolva os exercícios do capítulo 5 do livro do Thomaz, página 74 e 75 (pdf 44)