Linguagens Formais e Autômatos
Por: lolo lala • 22/5/2021 • Trabalho acadêmico • 708 Palavras (3 Páginas) • 171 Visualizações
[pic 1] | Bacharelado em Sistemas de Informação Linguagens formais e Autômatos - Trabalho |
Nome.: | RA: |
Prazo de entrega: até 18 de maio.
Questão 1: (0.5)Seja o alfabeto Σ = {*, 1, +, 0}. Assinale a alternativa que não apresenta uma palavra definida sobre o alfabeto Σ
a)0+0*+
b)0**
c)0+1=1
d)1
e)1*1.
Questão 2: (0.5) Considere a gramática G = (V, ∑ , P, S}, onde V = {S, X, Y}; ∑ = {a, b}, S é o símbolo inicial e P = { S → aX | b Y; X → bX | aY; Y→bY | a X| ε}
Assinale a alternativa que representa uma derivação correta.
a) S⇒bY⇒bbY⇒bbaX⇒bbaaY⇒bbaaε⇒bbaa.
b) S ⇒bY⇒bbY ⇒ bbaX ⇒ bbaaYY ⇒ bbaaεε ⇒ bbaa
c) S ⇒ aX ⇒abX ⇒abbX ⇒ abbbX ⇒abbbaY ⇒abbba ε ⇒abbba
d) S ⇒ aX ⇒ abaX⇒aba
e) S ⇒ aX ⇒ abX⇒abbX ⇒ abbbX⇒abbb
Questão 3:(0.5) - Considere a figura abaixo. Assinale a alternativa incorreta.
[pic 2]
- Trata-se de um autômato finito determinístico.
- g(q1,z)= {q1,q2}
- g(q0,x)={q0}
- O estado final é q2,segundo as convenções da representação gráfica.
- O estado inicial do autômato é q0, segundo as convenções da representação gráfica.
Questão 4: (0.5) Considere o autômato representado na figura abaixo e assinale a alternativa que apresenta a palavra aceita pelo mesmo.
[pic 3]
a)bacc
b)abcc
c)abca
d)abba
e)acab
Questão 5: (0.5) Para o autômato apresentado, assinale a alternativa que contemple o conjunto de produções P da gramática G = {V, ∑, P, S} que gera a Linguagem reconhecida por esta máquina de estados. Considerar: V = {Q0, Q1, Q2}, ∑ = {x, y,z} e Q0, o símbolo inicial da gramática.
[pic 4]
a) P = { Q0 → w Q0; Q1 →x Q2; Q2 → x Q2 | z Q2 | ε }
b) P = { Q0 → w Q0 | z Q2; Q1 →x Q2; Q2 → x Q2 |ε }
c) P = { Q0 → w Q0 | xQ1; Q1 → x Q2;Q2 → x Q2 | z Q2 | ε }
d) P = { Q0 → x Q0 | z Q1; Q2 → x Q2 | z Q2 | ε }
e) P = { Q0 → x Q0 | w Q1; Q1 →z Q2; Q2 → z Q2 | ε }
Questão 6: (0.5) Considere o alfabeto Σ = {a, b}.
A Linguagem L = {ω | ω = x* (xyx)*}.Assinale a alternativa que apresenta uma palavra que pertença a L
a)yxx
b)xyyx
c)xxyyxx
d) ε
e)yyyyy
Questão 7: (0.5) Considere-se a Gramática G = (V, T, P, E) onde:
...