Linguagens Formais e Autômatos

[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]

1. Trata-se de um autômato finito determinístico.
2. g(q1,z)= {q1,q2}
3. g(q0,x)={q0}
4. O estado  final é q2,segundo as convenções da representação gráfica.
5. 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: