Lista de Exercicios 01 LFA

Curso Superior de Ciência da Computação
Disciplina: LFA
Professor: Wanderson Rigo

Lista de Exercícios 01
1) Considere a seguinte gramática G, onde S é o símbolo inicial:
S  AcB
A  cA | aB
B  cB | aA
A
Assinale a alternativa que apresenta a palavra que NÃO pertence à linguagem gerada pela gramática G?
a) ccca
b) aaca
c) aaaca
d) ccac
e) caaac
2) Uma gramática G é definida por G=({x,y,z},{S,W,X,Y,Z}, P,S) na qual os membros de P são:
S  WZ
WX|Y
X  x | xX
Y  y | yY
Z  z | zZ
Qual das expressões regulares abaixo corresponde a esta gramática?
a) (xx* | yy*) zz*
b) xx* | yy* | zz*
c) xx* (yy* | zz*)
d) (xx | yy)* zz*
e) xx*yy*zz*
3) Considere o seguinte trecho de um programa:
1) i = 1;
2) while(i <= n){
3)
sum = sum + a[ i ];
4)
i = i + 1;
5) }
Considere que:
I representa a inicialização da variável i = 1 na linha 1;
T representa o teste da linha 2;
A representa os comandos da linha 3;
P representa o incremento na linha 4;

Qual é a expressão regular que representa todas as sequências de passos possíveis de serem executados por este trecho de programa?

a)
b)
c)
d)
e)

I(TAP)+
I(TAP)*
IT+A*P*
IT(AP)*
Nenhuma das alternativas.

4) Encontre as gramáticas regulares (GR) que denotam as seguintes expressões regulares (ER):
ER

GR

(0|1)*

S  0S | 1S | ε

001*

S ::= 0A
A ::= 0B
B ::= 1B | ε
S ::= 0A | 1B
A ::= 0S
B ::= 1 | 1C
C ::= 1B
S ::= aA
A ::= ε | aB | bC | cC
B ::= aA
C ::= bC | cC | ε

(00)*(11)+

a(aa)*(b|c)*

5) Determine L(G) onde G é dada por: a ) S  1S0S0 | 0S1S0 | 0S0S1 | ε
b) S  a B | b A | a | b
AaB|bC|a|b
BaD|bA|a|b
CaB|a
D  b A| b
6) Considere a seguinte gramática G, onde S é o símbolo inicial:
S  aS| Sb | c
Qual é a expressão regular que gera a mesma linguagem que a gramática G?
a) a*cb*
b) a+b+c
c) a+cb+
d) ca*b*
e) ca+b+

Divirta-se com os desafios!
“Algo só é impossível até que alguém duvide e resolva provar ao contrário.”
(Albert Einstein)