matematica discreta

FISI - Daniel Alfonso Quinto Pazce

TEORIA DE
LENGUAJES

GRAMATICA

VT ={conjunto de símbolos terminales}
S ={Símbolo especial de inicio}

P ={conjunto de reglas de producción}
P:
β

secuencia de símbolos terminales y
no terminales – sstn)
(

FISI- Daniel Alfonso Quinto Pazce

Una gramática G es una estructura
4-truple
G(VN , VT, S, P)
VN ={ conjunto de símbolos noterminales}

VOCABULARIO

VT ={a, b, c, …., z, 0, 1, +, -, *, /, cero, uno}
V*=(VN U VT )* contiene cadena vacía
V+={VN U VT }+

no contiene cadena vacía

FISI - Daniel Alfonso Quinto Pazce

Conjunto de símbolos terminales, y no terminales
para generar reglas de producción.
V= VN U VT
VN ∩ VT = Ø
VN ={ , , ,….,,….}

ALFABETO
FISI - Daniel Alfonso Quinto Pazce

Conjunto de símbolosterminales para generar una
gramática o elementos de un lenguaje
{an bm / n>0; m>0}
an bm
a b
aaa b
L(G) ={ab, aaab, abbb, aaabbb,…}
a bbb
aaa bbb

CONCATENACIÓN DE CADENAS
A1=A0 A
A2=A1 A
A3=A2 A

= C 1 U C2 U … U C n
C1 = abb
C2 = bbcc
C = C 1 U C2


=cadena

C = abb bbcc

FISI - Daniel Alfonso Quinto Pazce

Ak=Ak-1 A
A1 U A2 U A3 U …U Ak =

LONGITUD DE UNACADENA
Es el número de símbolos que componen una cadena.ICI=10
CLASIFICACION DE LA GRAMATICA SEGÚN NOAM
CHOMBSKY(1928-filadelfia)
GRAMATICA

REGLAS

T0

Con estructura de
frase sin restricciones



T1

SENSIBLE AL
CONTEXTO

β 
A ε VN
, β ε V*

T2

T3

LIBRE DE
CONTEXTO
REGULAR DE
KLENNE

β
,

 β
A ε VN
, β ε V*
,



δ ε V+

δ ε V+

 a
 a / A,B εVN , a ε Vt

FISI - Daniel Alfonso Quinto Pazce

TIPO

T0

Gramática con estructura de frase sin Restricciones

P:


2.

3.

4.

5.

6.

7.

8.

ARBOL:

1.























FISI - Daniel Alfonso Quinto Pazce



T1

GRAMATICA SENSIBLE AL CONTEXTO

P:
FISI - Daniel Alfonso Quinto Pazce


2.  a
3. ab
4. 
5. b  bb
6. b  bc
7. c  cc
1.

T2.-Gramática libre al contexto
P:

1.
3.
4.
5.

cd

ab

ab
A

B

b

a
T

FISI - Daniel Alfonso Quinto Pazce

2.

 ab
 ab
 cd
 a
 b

T3

G: REGULAR DE KLENNE

P:

1.
2.
3.
5.
6.
7.
8.

Estado de
Aceptación

a

A
S
b
b
a

Estado de
Atrapamiento

B
T

a

a

FISI -Daniel Alfonso Quinto Pazce

4.

 a
 b
 a
 b
 a
a
b
Є

DERIVACIÓN : de símbolos no terminales de una sstn, aplicando
Definición
Es una serie de sustituciones















1=>
2=> a
2=> aa
3=> aa ab
4=> aaab
4=> aaab
4=> aaa b
5=> aaab b
5=> aaabb b
6=> aaabbb c
7=> aaabbbc c
7=> aaabbbccc

FISI - Daniel AlfonsoQuinto Pazce

las reglas de producción de una gramática dada o generada.
Ej.:
Dada las reglas de producción derivar usando las reglas: 122344455677
P:
1.

2.
 a
3.
 ab
4.

5.
b  bb
6.
b  bc
7.
c  cc

MÉTODO DEL ÁRBOL DE DERIVACIÓN
Es una representación grafica de la derivación
Ejemplo: derivar (3 3 2 2 4)
P:
2.

3.
4.

Derivar: bc,

para obtener bbbccc:
bcb




c



c

Є

b
b b b

c c c

FISI - Daniel Alfonso Quinto Pazce

 ab
 b
 c
 Є

1.

Es el conjunto de secuencias de
símbolos terminales( sst ) del
Alfabeto.

FISI - Daniel Alfonso Quinto Pazce

LENGUAJE FORMAL

LENGUAJE GENERADO POR UNA
GRAMÁTICA : L(G)
Definición.- Dado una gramática G, el L(G) es el conjunto de

secuencias de símbolosterminales que pueden ser derivados a
partir del símbolo inicial ; L(G)={x/x ε Vt* y  ===>* x }

1.
2.
3.
4.

o‟

P:
1.
2.
3.

o‟

P:
1.
2.
3.
4.

 a
 a
 b
 Є


 a
 ab


 a
 a
 b

ab
aab
aaab
aaa…b

Tipo 2

Tipo 2

FISI - Daniel Alfonso Quinto Pazce

1. L(G)= {an b / n>0}
P:

GRAMÁTICA Vs

MAQUINA
a/1

a/1

A

S...