Gramaticas formales

UNIDAD 1
Para las gramáticas presentadas, se pide:
a) Indicar el tipo y nombre de cada de las gramáticas según la clasificación de Chomsky


Esta gramatica es de TIPO 2, estas gramáticas sedenominan “Independientes del contexto o de contexto libre”
---


Esta gramatica es de TIPO 0, estas gramáticas se denominan “Lenguajes estructurados por fases o recursivamente enumerables”
---Esta gramatica es de TIPO 3, estas gramáticas se denominan “Regulares o lineales”
---


Esta gramatica es de TIPO 1, estas gramáticas se denominan “Dependientes del contexto o sensiblesal contexto”
b) Obtener el Lenguaje de la gramática tipo 3 mediante árboles sintácticos












































c) Para elLenguaje de la gramática tipo 2:
- Obtener las palabras α = cbbcba y β = cbcaa que genera la gramática mediante derivaciones
Gramatica tipo 2


Mediante derivación:
S  BAa  cbAa  cbCaa  cbcaaAsi obtengo cbcaa=β.
S  BAa  AbAa  cbbAa  cbbcba
Asi obtengo cbbcba= α
- La palabra δ = cbabaa es ambigua demúestralo mediante sus árboles de derivaciones














Demuestroque δ =cbabaa es ambigua. Ya que se puede llegar a la misma palabra por 2 arboles diferentes.
UNIDAD 2

1
0 0

1 1
0
0 0,1
1 00 1

0 0
0 1 0 0,1
1
1

Tabla del grafo realizado
f
0
1
q0
q1
q11
q1
q4
q2
q2
q3
q11
*q3
q11
q11q4
q7
q5
q5
q6
q5
q6
q3
q11
q7
q11
q8
q8
q9
q11
q9
q10
q11
q10
q3
q11
q11
q11
q11

b) Definicion del autómata finito
AF={{0, 1}, {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9,q10, q11}, q0, {q3}, f}
3)

a)
1
1

1 2 1 2
2
2
2 1

b) Se elimina el estado “E” ya que NO es conexo. No es conexo ya que este estado no es accesible desde el estado...