Aula Pratica 5
Autómatos e Liguagens de Programação | Data: 09/03/2021; Hora:16:00; Duração: 2h; Sala:CLAV_136; Docente: Francisco Coelho
Resolução de Exercicios
Mostre que as seguintes linguagens não são regulares:
- ✓L1={1^n+1m =1 n+m: n,m≥0}.
- A linguagem das palavras capicua sobre {a,b}.
- L_3={aa^nb^n: n≥0}.
- L4={0n 1 n+1 : n≥0}.
Resolução ...
- L5={a n cb n : n≥0}.
Resolução ...
- L6={a n b m : m>n≥0}.
Pumping Lemma
Se L é Regular
a) Seja K o numero de estados de um AFD que acita L
Defina uma gramática independente do contexto que gere a linguagem:
- {wcw R : w∈{a,b} ∗ }.
- {wc n : w∈{a,b} ∗ e n=∣w∣}.
- {a i b j c k : k≥0 e i+j=k}.
- ✓ {a n b m : m,n≥0 e m != n}.
- dos números naturais sem zeros não significativos.
✓ Seja LL a linguagem de todas sequências de parêntesis, curvos - ‘((’ e ‘))’ - e rectos - ‘[’ e ‘]’ -, bem emparelhados. Pertencem a esta linguagem palavras como λ, “()()”, “[]”, “()()()[()]”, “(())([()])” e “(())([][([])])[]”. Não pertencem a LL palavras como “]”, “((”, “((]”, “(([)]”, “)()(” e “[()]]”.
- Mostre que LL não é regular;
- Defina uma gramática independente do contexto que gere LL.
Considere a gramática G=({A},{a,b},{A→AA ∣ aAb ∣ λ},A).
- Construa uma derivação esquerda para a palavra
aababb e a respetiva árvore de derivação.
- Construa uma derivação direita para a palavra
ababab e a respetiva árvore de derivação.
- Determine se G é ambígua. † Em caso afirmativo, apresente uma gramática não ambígua equivalente.
✓ Considere a gramática independente do contexto
G=({S},{a},{S→aa ∣ SS},S).
- Mostre que esta gramática é ambígua.
- † Apresente uma gramática equivalente não ambígua.
- Apresente uma gramática regular equivalente.
- Apresente uma expressão regular que represente a linguagem gerada pela gramática.