Ejercicios resultos de teoria de la computacion

1.- Escribe todas las palabras W; tal que |W|≤ 4 a partir de la expresión regular.
(x|y)*y(y|xy)*
Respuesta:
1) y 11) yxxx 21) xyyx
2) yy 12) yyyy 22) xxxy
3) yx 13) yxyx 23) xyxx
4) yyx 14) yxyy 24) xyxy
5) yxy 15) yyy 25) xxyy
6) yxx 16) xy 26) xxyx
7) yyxy 17) xyx
8) yxxy 18) xxy
9) yyxx 19) xyy
10) yyyx 20) xyyy

2.- Dada la gramática G; con reglas de producción.
1)q0→xxxq0yyy
2) q0→xy
Hallar:
i) L(G) = {(xxx)n xy (yyy)n|n≥o}
II) Tipo de Gramática = Gramática de tipo 2
Cadenas:
q0=>2 xy

q0=>1 xxxq0yyy
=>1 xxxxyyyy

q0 =>1 xxxq0yyy
=>1 xxxxxxq0yyyyyy
=>2 xxxxxxxyyyyyyy
3.- Dado el diagrama sintáctico.

X y
I
Y

Halla:
i) G
G= (V,S,I,→)
V= {I,I0,x,y}
S= {x,y}→:{ 1) I → x I0
2) I → y I
3) I0 → y
4) I0 → y I0 }
ii) L(G) = {yn xy ym|m,n≥0}
Cadenas:
I =>1 xI0
=>3 xy

I =>1 xI0
=>4 xyI0
=>4 xyyI0
=>3 xyyy

I =>2 yI
=>2 yyI
=>1 yyxI0
=>4 yyxyI0
=>4 yyxyyI0
=>3 yyxyyy

iii) Derivar una cadena W de tal manera que |w|≥ 7 (en árbol de derivación y derivación por partes.
Derivación por partes: Árbol dederivación
I =>2 yI y I
=>2 yyI y I
=>1 yyxI0 x I0
=>4 yyxyI0 y I0
=>4 yyxyyI0 y I0
=>4 yyxyyyI0 y I0
=>3 yyxyyyy y

4.- Dada la gramática:
1) S → MNz
2) M → aMa
3) M → z
4) N → bNb
5) N → z
Halla:
a) L(G) = {azazn U znbzbm|n≥1,m≥0}
b) Probar zaazaaabbzbbbz (enderivación por pasos y árbol de derivación)
No Existe la Cadena por que no es posible z seguido de a

5.- Sea la gramatica G con producciones.
a) I →oI
b) I → oT
c) T → &T
d) T → &
Hallar:
a) L(G)= {(oo)on&&m|n≥0,m≥0}
Cadenas:
I =>a oI
=>b ooT
=>c oo&T
=>d oo&&

I =>a oI
=>b ooT
=>d oo&

b) La expresión regular(oo)o*&&*

6.- Dado el diagrama sintáctico

I
( )

a

I

I
( )
I *

a
Hallar:
a) G
1) I → ( B
2) B → ) I
3) I → a I
4) I → I C
5) C→ ( I
6) I → *I
7) I → )
8) C → a

b) Probar
I =>* (((a)*(a*a))) No está dentro del L(G)
Cadenas:
I =>1 (B
=>2 ()I=>6 ()*I
=>7 ()*)

I =>6 *I
=>1 *(B
=>2 *()I
=>7 *())

7.- Escriba exactamente el lenguaje L(G) producido por la gramática G=(V,S, Λ,→)
V={ Λ,Γ,∆,S,+,(,)} S={(,),S,+} y el diagrama sintáctico.
→{ 1) Λ→(Λ)
2) Λ→S+Γ
3) Γ→S+∆
4) ∆→S+∆
5) ∆→S }
Cadenas:
Λ =>1 (Λ )
=>2 (S+Γ)
=>3 (S+ S+∆)
=>5 (S+ S+ S)Λ=>2 S+Γ
=>3 S+ S+∆
=>5 S+S+S

L(G)= {(n[S+]mS)n|n≥0,m≥2}

8.- Dado el diagrama sintáctico hallar.
a) G
1) Γ → □Γ
2) Γ → ~∆
3) ∆→ □∆
4) ∆→ □
b) L(G)={ □n~□□m|n≥0,m≥1
Cadenas:
Γ =>1 □Γ
=>1 □□Γ
=>1 □□□ Γ
=>2 □□□~∆
=>4 □□□~□

Γ =>1 □Γ
=>1 □□Γ
=>2 □□~∆
=>3 □□~□∆
=>3 □□~□□∆
=>3 □□~□□□∆
=>3 □□~□□□□∆
=>3□□~□□□□□∆
=>3 □□~□□□□□□∆
=>4 □□~□□□□□□□

c) La expresión regular.
□*(~□□)□*
d) Derivar una cadena tal que 9 ≥|U|≥ 11 (en árbol de derivación y en derivación por pasos)
Γ =>1 □Γ
=>1 □□Γ
=>2 □□~∆
=>3 □□~□∆
=>3 □□~□□∆
=>3 □□~□□□∆
=>3 □□~□□□□∆
=>3 □□~□□□□□∆
=>3 □□~□□□□□□∆
=>4 □□~□□□□□□□

Γ

~ ∆9.- Considere la gramática G=(N,T,→,∑) N={∑,Γ}, T={\,√}
→{ 1) ∑→√∑
2) ∑→\Γ
3) Γ→√Γ
4) Γ→√
Hallar:
a) L(G)= {√n\√m|n≥0,m≥1}
Cadenas:
∑=>1 √∑
=>2 √\Γ
=>4 √\√

∑=>1 √∑
=>1 √√∑
=>2 √√\Γ
=>4 √√\√
∑=>2\Γ
=>4 \√

b) La expresión regular asociada al L(G)
√*\√√*

11.- Dada la gramática
G=(N,T,→,S)

→{...