LFA Lista de Exerc cios 1

Prévia do material em texto

Professor Me Paulo David Linguagens Formais e Autômatos 
Lista de Exercícios 1 
 
 
1) O que é Linguagem Formal? 
 
2) O que é Autômato? 
 
3) No estudo de Linguagens Formais, o que Alfabeto? 
 
4) Marque os conjuntos que correspondem a um Alfabeto. 
 
Conjunto dos Números Inteiros 
Conjunto dos Números Naturais 
Conjunto do Números Primos 
Conjunto das Letras do Alfabeto Brasileiro 
Conjunto dos Algarismos Arábicos 
Conjunto dos Algarismos Romanos 
Conjunto {a, b, c, d} 
Conjunto das Partes de {a, b, c} 
Conjunto das Vogais 
Conjunto das Letras Gregas 
 
5) No estudo de Linguagens Formais, o que Palavra (String ou Cadeia de caracteres)? 
 
6) Na formação de Linguagens, com que estão relacionadas a Sintaxe e a semântica? 
 
7) O que é Comprimento de uma Palavra? 
 
8) O que é Prefixo, Sufixo e Subpalavra de uma Palavra? 
 
9) Apresente os possíveis prefixos, sufixos de cada uma das seguintes palavras: 
a) teoria 
b) universidade 
c) aaa 
d) abccba 
e) abcabc 
 
10) Como é definida a Concatenação sobre uma Linguagem? 
 
11) Realize a operação (100111)R. 
 
12) Calcule recursivamente |bab| (sobre o alfabeto {a,b}) e |01101| (sobre {0,1}). 
 
13) Encontre os prefixos, sufixos e substrings (subpalavra) do string (da palvra) 01011 sobre o 
alfabeto {0, 1}. 
 
14) Sejam L4 = {ba, baa, baaa, baaaa...} = {ban | n >= 1} e L5 = {aab, aabb, aabbb, aabbbb...} = 
{aabn | n >= 1}. Indique alguns strings para L4L5, 𝐋𝟓̅̅ ̅, L4.L5 e 𝐋𝟒
∗ . 
 
Faculdade Maurício de Nassau 
Curso: Sistemas de Informação 2017.2 
Disciplina: Linguagens Formais e Autômatos 
Professor Me. Paulo David 
 
 Professor Me Paulo David Linguagens Formais e Autômatos 
15) Como é definida a Gramática em Linguagens Formais? 
 
16) No estudo de Gramáticas em Linguagens Formais, o que é derivação? 
 
17) O que é Sistema de Estados Finitos? 
 
18) O que é Autômato Finito Determinístico (AFD)? 
 
19) Qual a linguagem que é aceita por Autômato Finito Determinístico (AFD)? 
 
20) Qual a linguagem que é aceita por Autômato Finito Não-Determinístico (AFND)? 
 
21) Considerando os três métodos dentre os mais empregados para a representação finita de 
linguagens, relacione a coluna da direita com a da esquerda. 
 
1 Metalinguagem A 
Correspondem a especificações finitas de dispositivos de 
geração de cadeias. Um dispositivo desse tipo deve ser 
capaz de gerar toda e qualquer cadeia pertencente à 
linguagem definida pela gramática, e nada mais. 
2 Gramáticas B 
Relacionam, de forma explícita e exaustiva, todas as 
cadeias pertencentes à particular linguagem a ser 
especificada. Toda e qualquer cadeia pertencente à 
linguagem deve constar desta relação. 
3 Reconhecedores C 
Nome dado à particular notação utilizada para representar 
uma linguagem, seja através de gramáticas ou de 
reconhecedores 
4 Enumerações D 
Correspondem a especificações finitas de dispositivos de 
aceitação de cadeias. Um dispositivo desse tipo deverá 
aceitar toda e qualquer cadeia pertencente à linguagem 
por ele definido, e rejeitar todas as cadeias não 
pertencentes à linguagem. 
 
Marque a alternativa que corresponde a correta correlação. 
a) 1A, 2B, 3C, 4D 
b) 1A, 2B, 3D, 4C 
c) 1B, 2D, 3A, 4C 
d) 1C, 2D, 3A, 4B 
e) 1D, 2A, 3D, 4B 
 
22) Uma Gramática é definida como sendo uma quádrupla G = (V, , P, S). Qual o significado de cada 
um dos símbolos que formam a gramática? 
 
23) Determine a Linguagem gerada pela Gramática G1. 
Onde: 
G1 = (V, Σ, R, S), onde: 
V = {S} 
Σ = {a, b} 
R = {S ↦ aSb, S ↦ } 
 
24) Determine a Linguagem gerada pela Gramática G2. 
Onde: 
G2 = (V, Σ, R, S), onde: 
V = {A,B,S} 
Σ = {0, 1} 
R = {S ↦ AB, A ↦ 0A11, A ↦ , B ↦ 0B, B ↦ } 
 
 Professor Me Paulo David Linguagens Formais e Autômatos 
25) Determine a Linguagem gerada pela Gramática G3. 
Onde: 
G3 = ({S, X, Y, A, B, F}, {a, b}, P, S), onde: 
P = {S ↦ XY, 
 X ↦ XaA | XbB | F, 
 Aa ↦ aA, Ab ↦ bA, AY ↦ Ya, 
 Ba ↦ aB, Bb ↦ bB, BY ↦ Yb, 
 Fa ↦ aF, Fb ↦ bF, FY ↦ } 
 
26) Um Autômato Finito Determinístico (AFD) é definido como sendo uma quíntupla M = (K, Σ, δ, 
s, F). Qual o significado de cada um dos símbolos que formam a quíntupla? 
 
27) Construa o Autômato Finito Determinístico M, com função de transição total, definido abaixo, tal 
que sua representação algébrica é M = (Q, Σ, δ, q0, F), onde: 
Q = {q0, q1, q2, q3} 
Σ = {0, 1, 2} 
F = {q1, q2} 
δ = {(q0, 0) → q0, (q0, 1) → q1, (q0, 2) → q3, 
(q1, 0) → q3, (q1, 1) → q1, (q1, 2) → q2, 
(q2, 0) → q3, (q2, 1) → q3, (q2, 2) → q2, 
(q3, 0) → q3, (q3, 1) → q3, (q3, 2) → q3} 
 
28) Seja o autômato finito determinístico a seguir, verifique se cada cadeia de caracteres a seguir é 
aceita pelo autômato: 
a) 0 
b) 1 
c) 01 
d) 011 
e) 01100000 
f) qual é o formato da linguagem que este autômato aceita? 
 
29) Seja M o autômato finito determinístico abaixo: 
 
δ a b 
q0 q0 q1 
q1 q2 q1 
q2 q2 q0 
 
a) Construa o diagrama de estados de M. 
b) Exiba as computações de M para as palavras abaa, bbbabb, bababa e ba. 
c) Quais as palavras do item b que são aceitas por M? 
d) Dê a expressão regular de L(M). 
 
30) Seja M um AFD cujo diagrama de estados é dado por: 
 
a) Construa a tabela que representa a função de transição para M. 
b) Quais, dentre as palavras baba, baab, abab e abaaab não são aceitas por M? 
c) Dê a ER para L(M).