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 L4L5, 𝐋𝟓̅̅ ̅, 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).