Computação

1) A partir da seguinte gramática G=(V,T,P,S), onde:
V={S,D}
T={0,1}
P={S->D|DS, D->00|11}
Reconhecer através de sequência de derivação e árvore de derivação as seguintes palavras:
a) 0011
S -> DS
-> 00D
-> 0011
S
/
D
/ \
00 D
|
11
b) 1101
S -> DS
-> 11S
NÃO RECONHECE
c) 001101
S -> DS
-> 00DS
-> 0011D
NÃO RECONHECE
d) 111100
S ->
->
->
->

DS
11DS
1111D
111100

S
/
D
/ \
11 D
/ \
11
D

|
00
Finalmente, qual é a expressão regular que representa essa linguagem? Palavras que compostas por uma sequência de dois 0's ou dois 1's
2) A partir da seguinte gramática G=(V,T,P,S), onde:
V={S,D,E}
T={0,1}
P={S -> D|E, D -> 0D0 | 1D1 | E, E -> 0|1}
Reconhecer através da sequência de derivação a árvore de derivação as seguintes palavras:
a) 101
S ->
->
->
->

D
1D1
1E1
101

S
/
D
/
1D1
|
E
|
0
b) 001100
S -> D
-> 0D0
-> 00D00
-> 001D100
NÃO RECONHECE
c) 101101
S -> D
-> 1D1
-> 10D01
-> 101D101
NÃO RECONHECE
d) 0011

S ->
NÃO RECONHECE
e) 000
S ->
->
->
->

D
0D0
0E0
000

S
/
D
/ \
D 0D0
|
E
|
0
f) 10101
S ->
->
->
->
->

D
1D1
10D01
10E01
10101

S
\
D
/ \
1D1
D
/ \
0D0 E
|
1
Finalmente, qual é a expressão regular que representa esta linguagem? Palavras compostas de 0's e 1's intercalados.
3) A partir da seguinte gramática G={V,T,P,S), onde:
V={S,A,B,C}
T={i,d,.}
P={S->A|B|B.B, A->i|iC, C->iC|i|dC|d, B->dB|d }
Reconhecer...

a) ididi
S ->
->
->
->
->
->

A iC idC idiC ididC ididi b) dddd
S ->
->
->
->
->

B dB ddB dddB dddd

c) ddidd
S ->
NÃO RECONHECE
d) dd.dd
S -> B.B
-> dB.dB
-> dd.dd
Qual é a expressão regular que representa esta linguagem?
4) A gramática G=(V,T,P,S) onde:
V={S,D}
T={0,1}
P={S->D, S->DS, D->0|1}
Reconhece:

01001
S ->
->
->
->
->
->

DS
0DS
01DS
010DS
0100D
01001

S ->
->
->
->
->

DS
1DS
10DS
101D
1011

1011

1111

S ->
->
->
->
->