Lista Resolvida - Compiladores

Prévia do material em texto

Apresente com a notação formal de conjuntos a gramática regular equivalente à expressão regular (aa)∗. Dê três exemplos de sentenças válidas na correspondente linguagem regular. 
(aa)* = L {W = {aa}*}
λ -> reconhece
aa -> reconhece
aaaa -> reconhece
2) Apresente com a notação formal de conjuntos a gramática regular equivalente à expressão regular a(b|c)∗. Dê três exemplos de sentenças válidas na correspondente linguagem regular.
a(b|c)* => L = {w    a (b,c)*}
a -> reconhece
abbcc -> reconhece
abbbbcccc -> reconhece
3) Apresente com a notação formal de conjuntos a gramática regular equivalente à expressão regular ba|a∗b. Dê três exemplos de sentenças válidas na correspondente linguagem regular.
ba|a*b => L = {w   (ba,a)*b}
b-> reconhece
baaaab -> reconhece
aaaaab -> reconhece
4) Apresente com a notação formal de conjuntos a gramática regular equivalente à expressão regular x∗(y|z)z∗. Dê três exemplos de sentenças válidas na correspondente linguagem regular
x*(y|z)z* => 
y -> reconhece
xxxxyzzz -> reconhece
xxx z -> reconhece 
6) Construa o Autômato finito determinístico para reconhecer a expressão regular (0|1)∗0
0
0|1
q2
q1
7) Considere a gramática Ga = ({a}, {S,N, Q,R}, P, S), com o conjunto de produções P com os elementos S → QNQ QN → QR RN → NNR RQ → NNQ N → a Q → ε
(a) Qual é a classificação de Ga pela hierarquia de Chomsky? 
(b) Dê quatro exemplos de sentenças que podem ser derivadas a partir do símbolo sentencial S.
 (c) A partir de sua resposta para o item anterior, descreva informalmente qual é a linguagem representada por essa gramática
 Gramáticas sensível ao contexto (Tipo 1)
QND -> EAE -> A
QND -> QRQ ->QNNQ -> aa
QNQ -> QNQ -> QNNQ -> QRNQ -> QNNRQ -> QRNRQ -> QNNRRQ -> EaaRRQ -> aaRNQ
A linguagem permite formar palavras contendo apenas a da forma (1,2,4,8..) sempre sendo multiplicado por 2.
8) Apresente, para a seguinte gramática expressa em notação BNF, na qual o símbolo sentencial é:
 (a) A notação formal de conjuntos. (b) A representação na notação de diagrama sintático. (c) Três exemplos de sentenças da linguagem descrita pela gramática, com a sequência de derivações para cada caso
a) (a,b,i,j,(,},{,S,M,N,(,S -> (M) | a|b, M -> M; N|N; S|S,s)
b) a: S => a
 b: S=> (M) => (N) => (S) =>(b)
(a;b;a) = S=>(M) =>(M;N) =>(N;N) => (S;N) => (S;N;S) => (S;S;S) => (a;S;S) => (a;b;S) =>(a,b,a)
9) Considere a gramática Gb = {Vt, Vn, P, S}, com Vt = {a, b}, Vn = {A, S} e as produções P = {S → A, A → aAb, A → ab}. 
(a) Represente a gramática em notação BNF.
(b) Represente a gramática em diagramas sintáticos. 
(c) Apresente uma sequência de derivações que resulte na sentença aabb.
a. Gramatica livre de contexto (Tipo 2)
b) <s> :: = <A>
 <A> ::= a < A > b | ab
c) S -> A _>
10) Considere a gramática Gd = ({x, y,+,×, (, )}, {E}, P, E) onde P é o conjunto com as seguintes produções: E → E + E E → E × E E → (E) E → x E → y
(a) Represente a gramática em notação BNF. 
(b) Represente a gramática em notação de diagramas sintáticos.
(c) Apresente duas derivações distintas cujo resultado seja a sentença x + x × y.
<s> :: = <A>x <B>y <C>
<A> ::= x <A> x
<B> ::= <B> y
<C> ::= z <A> z
c) S = AxByC => xAxxByC => xxx ByC => xxxByyC => xxxyyC => xxxyyzAz => xxxyyzuxAxx => xxxyyzxxz