Exercícios de LFA

Estes exercícios destinam-se a ser feitos pelos alunos fora das aulas. As soluções propostas poderão ser entregues ao docente para correcção ou poderão ser discutidas no horário de atendimento. Estão disponíveis possíveis resoluções para os exercícios assinalados com (s).

NB: Estes enunciados deverão ser lidos num ambiente que mostre a letra lambda (λ), assim como índices superiores e inferiores. Agradeço que qualquer dificuldade em os visualizar me seja comunicada.

Definições recursivas de conjuntos

Construa definições recursivas dos seguintes conjuntos, onde Σ = {a,b} é um alfabeto.
1. C₁ = { palavras sobre Σ em que o símbolo a ocorre aos pares }.
  (C₁ inclui, por exemplo, bbaab e aaaa, mas não inclui aaa ou aabaaaba.)
2. C₂ = { w | w ∈ Σ^*, |w| é par, w começa por a e, em w, os a's e os b's ocorrem alternados }.
3. C₃ = { w | w ∈ Σ^* e w é capicua }.
4. (s) C₄ = { aⁿbⁿ | n > 0 }.
  (Nota: a^k representa k ocorrências consecutivas do símbolo a).
5. C₅ = { aⁱb^j | 0 ≤ i < j }.
6. (s) C₆ = { w | w ∈ Σ^* e o número de a's em w é igual ao de b's }.
  (Sugestão: use a concatenação de palavras no passo recursivo.)

Subpalavras, prefixos e sufixos

Liste todas as subpalavras, todos os prefixos e todos os sufixos das seguintes palavras sobre o alfabeto {0,1,2,3}:
1. 01023;
2. 11111;
3. λ.

Conjuntos

Dê exemplos de palavras que pertencem e que não pertencem a cada um dos seguintes conjuntos, onde T = {a,b}:
1. L₁ = { w | existe u pertencente a TT tal que w=uu^Ru };
2. L₂ = { w | w ∈ T^* e ww=www };
3. L₃ = { w | existem u e v pertencentes a T^* tais que uvw=wvu }.
Para cada um dos conjuntos da pergunta anterior, diga, justificando, se é ou não regular.

Expressões regulares

Construa uma expressão regular que represente os números reais sem sinal escritos de acordo com as seguintes regras:
- um número real tem sempre uma vírgula;
- um número real começa por 0 se e só se a sua parte inteira é 0;
- um número real acaba em 0 se e só se a sua parte decimal é 0.
Construa expressões regulares que representem as linguagens indicadas.
1. (s) A linguagem das palavras sobre {a,b,c} em que todos os a's precedem todos os b's que, por sua vez, precedem todos os c's (donde que todos os a's precedem todos os c's), podendo não haver nem a's, nem b's, nem c's.
2. (s) A linguagem da alínea anterior sem a palavra vazia.
3. As palavras sobre {a,b,c} de comprimento inferior a 3.
4. As palavras sobre {a,b,c} que começam por a, acabam em cc e têm exactamente dois b's.
5. A linguagem das palavras sobre {a,b} que têm aa e bb como subpalavras.
6. As palavras sobre {a,b} de que bba não é subpalavra.
7. (s) A linguagem das palavras sobre {a,b} que não têm prefixo aaa.
8. (s) A linguagem das palavras sobre {a,b} que não têm aaa como subpalavra.
9. As palavras sobre {x,y} em que xy não ocorre.
10. As palavras sobre {x,y} em que xy ocorre.
11. As palavras sobre {x,y} em que xy só ocorre uma vez.
Descreva, informalmente, as linguagens representadas pelas expressões regulares seguintes:
1. (a ∪ b ∪ c)(a ∪ b ∪ c)^*;
2. (a ∪ b)((a ∪ b)(b ∪ a))^*;
3. 5 ∪ (1 ∪ 2 ∪ ... ∪ 9)(0 ∪ 1 ∪ ... ∪ 9)^*(0 ∪ 5);
4. c^*(a ∪ b)(a ∪ b ∪ c)^*; e
5. (a(b ∪ c)^*a ∪ b ∪ c)^*.
Simplifique as expressões regulares seguintes:
1. (s) ∅^* ∪ a^* ∪ b^*(a ∪ b)^*;
2. aa^*b ∪ b;
3. (s) b^*(a ∪ (b^*a^*)^*)ab^*(ab^*)^*b;
4. (+) (a^*b)^* ∪ (b^*a)^*.

Autómatos finitos deterministas

Para o autómato finito determinista M = ({q₀, q₁, q₂}, {a,b}, δ, q₀, {q₂}), com a função de transição δ dada pela tabela

δ a b

q₀ q₀ q₁
q₁ q₂ q₁
q₂ q₂ q₀
1. Desenhe o diagrama de estados.
2. Escreva as computações de M para as palavras abaa e bbbabb, referindo se as palavras são aceites ou não.
3. Escreva uma expressão regular que represente a linguagem reconhecida por M.
Seja M = ({q₀, q₁, q₂}, {x,y}, {(q₀,x,q₁), (q₀,y,q₀), (q₁,x,q₁), (q₁,y,q₂), (q₂,x,q₁), (q₂,y,q₀)}, q₀, {q₀}) um autómato finito determinista.
1. Desenhe o diagrama de estados.
2. (s) Escreva uma expressão regular que represente a linguagem reconhecida por M.
3. (s) Repita a alínea anterior para o autómato finito determinista M' que só difere de M no conjunto de estados de aceitação, que no caso de M' é {q₀, q₁}.
Construa um autómato finito determinista que reconheça a linguagem das palavras sobre {a,b,c} em que todos os a's precedem todos os b's que, por sua vez, precedem todos os c's (donde que todos os a's precedem todos os c's), podendo não haver nem a's, nem b's, nem c's
Construa um autómato finito determinista que reconheça a linguagem das palavras sobre {a,b} que não têm aa como subpalavra.
Construa um autómato finito determinista que reconheça a linguagem das palavras sobre {a,b,c} em que cada b é seguido imediatamente por cc.
Construa um autómato finito determinista que reconheça a linguagem das palavras não vazias sobre {a,b} em que o número de a's é divisível por 3.
Construa um autómato finito determinista que reconheça L((ab)^*(ba)^*).
Defina um AFD que reconheça a linguagem do exercício 5.

δ	a	b

q₀	q₀	q₁
q₁	q₂	q₁
q₂	q₂	q₀

Autómatos finitos não deterministas

Considere a linguagem de todos os números inteiros sem sinal, escritos em base 3, em que o último algarismo ocorre anteriormente no número. Por exemplo, 1202 e 00 pertencem a esta linguagem, mas 1002 e 1 não. (Os números escritos em base 3 só podem ter os algarismos 0, 1 e 2.)
1. Escreva uma expressão regular que a represente.
2. Defina um autómato finito que a reconheça.
3. (+) Apresente um autómato finito determinista que a reconheça. (Sugestão: tente construí-lo directamente, sem recorrer a qualquer algoritmo.)
Seja M = ({0,1,2}, {a,b,c}, δ, 0, {1,2}) um autómato finito não determinista cuja função de transição δ é

δ a b c λ

0 {0} {1} {2}
1 {1}
2 {1,2}
Construa um autómato finito determinista equivalente a M, usando o algoritmo dado nas aulas, e apresente uma expressão regular que represente a linguagem por ele reconhecida.
(s) Repita o exercício anterior para o autómato finito não determinista N = ({0,1,2,3}, {m,n}, δ, 0, {1}), cuja função de transição δ é

δ m n λ

0 {1} {2} {1}
1 {1,3}
2 {3}
3 {1,3} {2}
(s) Considere a linguagem de todas as palavras sobre {a,b} em que o antepenúltimo símbolo é b.
1. Defina um autómato finito (não determinista) que reconheça esta linguagem.
2. Aplicando o algoritmo dado nas aulas, construa um autómato finito determinista equivalente ao autómato finito da alínea anterior.
(+) Repita o exercício anterior para a linguagem de todas as palavras sobre {a,b} em que o terceiro e o antepenúltimo símbolos são b. São exemplos de palavras que pertencem a esta linguagem as palavras aababaa, abbbbbbbb, abba e bbb.
Sejam M₁ = (Q₁, T, δ₁, q₀₁, F₁) e M₂ = (Q₂, T, δ₂, q₀₂, F₂) dois autómatos finitos tais que Q₁ e Q₂ são disjuntos.
Defina um autómato finito M₁₂ tal que L(M₁₂) = L(M₁) ∪ L(M₂)

δ	a	b	c	λ

0	{0}		{1}	{2}
1			{1}
2		{1,2}

δ	m	n	λ

0	{1}	{2}	{1}
1		{1,3}
2			{3}
3	{1,3}	{2}

Minimização de autómatos finitos deterministas

(s) Aplicando o algoritmo dado nas aulas, construa o autómato finito determinista mínimo equivalente a M = ({A,B,C,D,E,F}, {a,b}, δ, A, {B,D}), com a função de transição dada na tabela

δ a b

A B E
B E C
C D F
D F C
E F F
F E F
e apresente uma expressão regular que represente L(M).
Considere o autómato finito não determinista M = ({1,2,3,4,5}, {x,y}, δ, 1, {5}), com a função de transição dada na tabela

δ x y

1 {1} {1,2}
2 ∅ {3}
3 {3} {3,4}
4 ∅ {5}
5 {5} {5}
1. Construa o AFD equivalente a M.
2. Construa o AFD mínimo equivalente a M.
(s) Considere a linguagem representada por (aaa)^* reunida com (aa)^*.
1. Defina um autómato finito (não determinista) que reconheça aquela linguagem.
2. Construa o AFD equivalente ao autómato finito definido na alínea anterior.
3. Construa o AFD mínimo equivalente ao AFD obtido na alínea anterior.
Repita o exercício anterior para a linguagem das palavras sobre {a,b,c} que têm ababc como subpalavra.

δ	a	b

A	B	E
B	E	C
C	D	F
D	F	C
E	F	F
F	E	F

δ	x	y

1	{1}	{1,2}
2	∅	{3}
3	{3}	{3,4}
4	∅	{5}
5	{5}	{5}

Pumping Lemma

Mostre que a linguagem L = {1ⁿ+1^m=1^n+m | n,m ≥ 0} não é uma linguagem regular.
Mostre que a linguagem das palavras capicuas sobre {a,b} não é uma linguagem regular.

Gramáticas independentes do contexto

Desenvolva uma gramática independente do contexto que gere a linguagem { wcw^R | w ∈ {a,b}^*}.
Desenvolva uma gramática independente do contexto que gere a linguagem { wcⁿ | w ∈ {a,b}^* e n=|w| }.
Desenvolva uma gramática independente do contexto que gere a linguagem { aⁱb^jc^k | k ≥ 0 e i+j=k }.
(s) Construa uma gramática independente do contexto que gere a linguagem { aⁿb^m | m,n ≥ 0 e m ≠ n }.
Defina uma gramática independente do contexto que gere os naturais sem zeros não significativos.
Defina uma gramática independente do contexto que gere os reais (incluindo os negativos) em que: a parte inteira é não vazia e não tem zeros não significativos; a parte decimal é não vazia e só termina em zero se for constituída por um único 0; e as partes inteira e decimal são separadas por uma vírgula.
Seja L 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 L palavras como “]”, “(”, “(]”, “([)]”, “)(” e “[()]]”.
1. Mostre que L não é regular.
2. Defina uma gramática independente do contexto que gere L.
(s) Considere um conjunto V de variáveis e um conjunto F de símbolos de função, cada um com uma aridade maior que ou igual a zero. Um termo é definido como:
- uma variável é um termo;
- um símbolo de função de aridade 0 é um termo;
- se t₁, t₂, ..., t_k, k > 0, são termos, então, para todos os símbolos de função f de aridade k, f(t₁, t₂, ..., t_k) é um termo;
- nada mais é um termo.
Defina uma gramática independente do contexto que gere os termos descritos. (Use os símbolos v e f como representantes das variáveis e dos símbolos de função, respectivamente. Exemplos de termos são v, f, f(v) e f(v,f(f(f),f)). )
Considere a gramática G = ({A}, {a,b}, {A -> AA | aAb | λ}, A).
1. Construa uma derivação esquerda para a palavra aababb e a respectiva árvore de derivação.
2. Construa uma derivação direita para a palavra ababab e a respectiva árvore de derivação.
3. Determine se G é ambígua. Em caso afirmativo, apresente uma gramática não ambígua equivalente.
(s) Considere a gramática independente do contexto G = ({S}, {a}, {S -> aa | SS}, S).
1. Mostre que a gramática é ambígua.
2. Apresente uma gramática equivalente não ambígua.
3. Apresente uma gramática regular equivalente.
4. Apresente uma expressão regular que represente a linguagem gerada pela gramática.
Resolva o exercício anterior para a gramática G = ({S,A}, {a}, {S -> λ | AS, A -> λ | a}, S)

Autómatos de pilha

Defina um autómato de pilha que reconheça a linguagem { w | w ∈ {a,b}^* e w = w ^R }. Será possível definir um autómato de pilha determinista que reconheça esta linguagem? Justifique a sua resposta.
(s) Defina um autómato de pilha que reconheça L = { 1ⁿ + 1^m = 1^m+n | n,m ≥ 0 } e indique se ele é determinista ou não determinista.
Considere a linguagem de todas as palavras sobre {a,b} em que o número de a's é igual ao número de b's.
1. Defina um autómato de pilha não determinista que a reconheça.
2. (+) Defina um autómato de pilha determinista que a reconheça.
Construa um autómato de pilha que reconheça a linguagem { c²ⁱd³ⁱ | i ≥ 0 }.

Normalização de gramáticas independentes do contexto

Considere a gramática independente do contexto G = ({S,B,C}, {a,b,c}, P, S), com P o conjunto de produções
S -> aS | bS | B
B -> bb | C | λ
C -> cC | λ
1. Escreva uma expressão regular que represente a linguagem gerada por G.
2. Construa uma gramática (essencialmente) não contraível equivalente.
3. Elimine as produções unitárias da gramática obtida na alínea anterior.
Repita o exercício anterior para a gramática G = ({S,A,B,C}, {a,b,c}, P, S), com produções P
S -> ABC | λ
A -> aA | a
B -> bB | A
C -> cC | λ
Repita o exercício anterior para a gramática G = ({S,A,B}, {a,b}, P, S), com produções P
S -> BSA | A
A -> aA | λ
B -> Bba | λ
Construa uma gramática equivalente a G = ({S,A,B,C}, {a,b,c}, P, S), com produções P
S -> A | B | C
A -> aa | B
B -> bb | C
C -> cc | A
que não contenha produções unitárias e escreva uma expressão regular que represente a linguagem gerada por esta gramática.
Construa uma gramática equivalente a G = ({S,A,B,C,D,E,F,G}, {a,b}, P, S), com produções P
S -> aA | BD
A -> aA | aAB | aD
B -> aB | aC | BF
C -> Bb | aAC | E
D -> bD | bC | b
E -> aB | bC
F -> aF | aG | a
G -> a | b
sem símbolos inúteis e encontre uma expressão regular que represente a linguagem gerada por esta gramática.
Construa uma gramática equivalente a G = ({S,A,B,C}, {a,b,c}, P, S), com produções P
S -> aAbB | ABC | a
A -> aA | a
B -> bBcC | b
C -> abc
na forma normal de Chomsky.
(s) Construa uma gramática equivalente a G = ({A,B}, {a,b}, P, A), com produções P
A -> aAb | B
B -> Bb | λ
na forma normal de Greibach.
Repita o exercício anterior para a gramática G = ({S,A,B}, {a,b}, P, S), com produções P
S -> A | B
A -> AAA | a | B
B -> BBb | b

Gramáticas LL(1)

Calcule os símbolos directores e determine se as seguintes gramáticas são LL(1):
1. G1 = ({S,A,B}, {a,b,c,#}, {S -> AB#, A -> aAb | B, B -> aBc | λ}, S)
2. G2 = ({S,A,B,C}, {a,b,c,d,#}, {S -> ABC#, A -> aA | λ, B -> bBc | λ, C -> cA | dB | λ}, S)
3. (s) G3 = ({S,A,B,C,D}, {a,b,c,d,#}, {S -> aAd#, A -> BCD, B -> bB | λ, C -> cC | λ, D -> bD | λ}, S}
Modifique a gramática G = ({S,A,B,C}, {a,b,c,#}, P, S) de modo a obter uma gramática LL(1) equivalente. As produções P de G são:
S -> aA# | abB# | abcC#
A -> aA | λ
B -> bB | λ
C -> Cc | λ
Defina uma gramática LL(1) que gere a linguagem das expressões aritméticas com subtracção, multiplicação e parêntesis. (Use o símbolo n para representar os inteiros.)

Gramáticas LR(0)

Considere a gramática G = ({S,A,B}, {a,b,#}, {S -> aBA#, A -> b | aB, B -> a | bB}, S).
1. Construa o autómato dos itens válidos de G.
2. Diga, justificando, se G é LR(0).
3. Construa a tabela de análise sintáctica para G.
4. Defina o autómato de pilha reconhecedor LR(0) para G.
Repita as duas primeiras alíneas do exercício anterior para a gramática G = ({S,A,B}, {a,b,#}, {S -> aA# | AB#, A -> aAb | b, B -> ab | b}, S). Se a gramática não é LR(0), enumere os conflitos encontrados.
Repita o exercício anterior para a gramática G = ({X,Y,Z}, {0,1,#}, {X -> ZY# | 1YZ#, Y -> 0Y | λ, Z -> Z1 | 1}, X).

Gramáticas LR(1)

(s) Considere a gramática G = ({S,A,B}, {a,b}, P, S), com P o conjunto de produções:
S -> AB
A -> aA | λ
B -> Bb | λ
1. Construa o autómato dos itens LR(1) válidos de G.
2. Diga, justificando, se G é LR(1).
3. Construa o autómato amalgamado e diga, justificando, se G é LALR(1).
4. Construa a tabela de análise sintáctica LR(1) para G.
5. Com base no autómato dos itens válidos de G, defina o autómato de pilha reconhecedor LR(1).
6. Construa a computação do autómato de pilha para a palavra aabb.
(s) Repita o exercício anterior com a gramática G = ({S,A,B}, {a,b}, P, S), com P o conjunto de produções:
S -> ABA
A -> Aa | λ
B -> bB | b
(s) Repita as primeiras 4 alíneas do exercício anterior com a gramática G = ({S}, {a}, P, S), com P o conjunto de produções:
S -> aSa | λ
(Se G não é LR(1), não faça as alíneas que não se aplicam.)
Repita o exercício anterior com a gramática G = ({S,E,F}, {w,x,y,z}, P, S), com P o conjunto de produções:
S -> Ex | yEw | Fw | yFx
E -> z
F -> z
Repita o exercício anterior com a gramática G = ({S,C}, {c,d}, P, S), com P o conjunto de produções:
S -> CC
C -> cC | d
Repita o exercício anterior com a gramática G = ({E,T}, {i,+,(,)}, P, E), com P o conjunto de produções:
E -> E+T | T
T -> i | (E)

Computabilidade

Mostre que determinar se o programa p inicializa a variável X quando corrido com dados (input) d é indecidível. (Um programa inicializa a variável X se executa uma instrução X := e, tal que X não ocorre na expressão e.)
(s) Mostre que o problema de decisão "o programa p executa a instrução i quando corre com dados nil?" é indecidível. (A instrução i pode ser, por exemplo, X := 0.)
Mostre que o problema de decisão "o programa p termina para algum valor dos dados?" é indecidível.
Mostre que o problema de decisão "o programa p termina para todos os dados?" é indecidível.
Mostre que determinar se a variável X toma o valor d nalgum ponto da execução do programa p com dados d é indecidível.

Nota

Os exercícios assinalados com (+) são de resolução mais complicada ou mais trabalhosa que os restantes.