Linguagem Formais e Autômatos lista Exercícios

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Lista de Exercícios_Capítulo 2.pdf
Lista de Exercícios - Capítulo 2
1) Seja a seguinte gramática G = ( N, T, P, S ), onde:
N = {S, X}
Τ = {a, b}
P = {S → XX, X → a, A → bX, A → Xb}
S = {S}
Determine 02 sentenças de L(G) que podem ser formadas com derivações de 4 passos. 
2) Seja a seguinte gramática G = ( N, T, P, S ), onde: 
N = {X, Y}
T = {x, y, z, t}
P = { X → xXzt | Y, Y → y|xy|ε}
S = {X}
Verifique se é possível gerar as sentenças abaixo. Justifique mostrando todas as formas sentenciais 
atingidas. Se não for possível, explique o motivo. 
a) xxyzt
b) xxztzt
c) xxzt
3) Escrever a gramática do exercício anterior no formato G = ( V, Σ, P, S ).
4) Para a gramática G = ( N, T, P, S ), onde:
N = {E,S} 
T = {n, /, - } 
P = {EE / S | n, S S - S | n }
S= {E}
Apresentar todos os passos da geração de uma árvore de derivação das sentenças, justificando caso 
não seja possível: 
a) n / n - n 
b) n - n / n 
5) Para a gramática G = ({S}, {+,-,x,y}, {SS+S|S-S|x|y|-S},S) apresentar duas árvores de 
derivação distintas para a cadeia: -y+x-y. 
Lista de Exercícios_Capítulo 4.pdf
Lista de Exercícios - Capítulo 4 
1) Representar o autômato abaixo no formato de tabela de transições e diagramas de 
estados: 
M = (K, Σ, δ, e0, F), onde: 
 K = (1, 2, 3, 4) Σ = (a, b, c, d, e, f) e0 = 1 F = (3 , 4) 
δ(1, a) → 2 δ(2, b) → 2 δ(2, c) → 3 δ(2, f) → 4 δ(3, d) → 2 
δ(3, e) → 1 δ(4, a) → 4 δ(4, e) → 3 
 
2) Verificar se as seguintes cadeias podem ser reconhecidas pelo autômato do 
exercício anterior, explicando o motivo caso não sejam: 
a) abbb 
b) abc 
c) ae 
d) afaaa 
e) afe 
3) Para o autômato finito representado na Tabela de Transições abaixo, pede-se: 
a) Representá-lo na notação de Produções do Autômato (M = (K, ΣΣΣΣ, δδδδ, e0, F)); e 
b) Obter a gramática regular correspondente. 
 
 + * / 
X X Z Y 
Y W Z 
W X Y Z 
Z Y W 
 
4) Para o autômato finito representado na Tabela de Transições abaixo, pede-se: 
a) Representá-lo no formato de Diagrama de Estados; 
b) Representá-lo no formato de Produções do Autômato; 
c) Obter a gramática regular correspondente. 
d) Verificar se as sentenças: wwy e wxyx podem ser geradas na gramática do letra c. 
 
 x y z w 
A B D A 
B C B 
C D A C 
D C B 
 
5) Escreva autômatos finitos determinísticos para o reconhecimento de cadeias sobre o 
alfabeto {0,1} de acordo com as seguintes regras de formação: 
a) Possui vários (0 ou mais) uns seguindo por 1 zero. 
b) Possui no mínimo 1 zero e um. 
c) Começa com um e termina com zero. 
d) Possui comprimento menor ou igual a 2. 
e) Possui número ímpar de uns. 
f) Possui pelo menos 2 zeros consecutivos.