tema 4.tema 4.- --- gramáticas regularesgramáticas regulares · 2019-07-18 · obtención de una...

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES

UNIVERSIDAD DE CÓRDOBAUNIVERSIDAD DE CÓRDOBAUNIVERSIDAD DE CÓRDOBAUNIVERSIDAD DE CÓRDOBAESCUELA POLITÉCNICA SUPERIORESCUELA POLITÉCNICA SUPERIORESCUELA POLITÉCNICA SUPERIORESCUELA POLITÉCNICA SUPERIOR

DEPARTAMENTO DE INFORMÁTICA Y ANÁLISIS NUMÉRICODEPARTAMENTO DE INFORMÁTICA Y ANÁLISIS NUMÉRICODEPARTAMENTO DE INFORMÁTICA Y ANÁLISIS NUMÉRICODEPARTAMENTO DE INFORMÁTICA Y ANÁLISIS NUMÉRICO

INGENIERÍA TÉCNICA EN INFORMÁTICA DE SISTEMASINGENIERÍA TÉCNICA EN INFORMÁTICA DE SISTEMASINGENIERÍA TÉCNICA EN INFORMÁTICA DE SISTEMASINGENIERÍA TÉCNICA EN INFORMÁTICA DE SISTEMAS

SEGUNDO CURSO, SEGUNDO CUATRIMESTRESEGUNDO CURSO, SEGUNDO CUATRIMESTRESEGUNDO CURSO, SEGUNDO CUATRIMESTRESEGUNDO CURSO, SEGUNDO CUATRIMESTRE

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES

Tema 4.Tema 4.Tema 4.Tema 4.Tema 4.Tema 4.Tema 4.Tema 4.-------- GramáticasGramáticasGramáticasGramáticasGramáticasGramáticasGramáticasGramáticas regularesregularesregularesregularesregularesregularesregularesregulares

Gramática de tipo 3 o regularGramática de tipo 3 o regularGramática de tipo 3 o regularGramática de tipo 3 o regular

Las reglas son de la forma

Α → β ∈ P

donde

A ∈ VN

aB

Teoría de Autómatas y Lenguajes FormalesTeoría de Autómatas y Lenguajes FormalesTeoría de Autómatas y Lenguajes FormalesTeoría de Autómatas y Lenguajes FormalesTeoría de Autómatas y Lenguajes FormalesTeoría de Autómatas y Lenguajes FormalesTeoría de Autómatas y Lenguajes FormalesTeoría de Autómatas y Lenguajes Formales Tema 4.Tema 4.Tema 4.Tema 4.Tema 4.Tema 4.Tema 4.Tema 4.-------- GramáticasGramáticasGramáticasGramáticasGramáticasGramáticasGramáticasGramáticas regularesregularesregularesregularesregularesregularesregularesregulares

2222

∈

B ∈ VN , a ∈ VT

=ε

β a

aB

Gramática de tipo 3 o regular: ejemploGramática de tipo 3 o regular: ejemploGramática de tipo 3 o regular: ejemploGramática de tipo 3 o regular: ejemplo

P1 = {

(1) S → letra

(2) S → letra A

(3) A → letra


3333

(3) A → letra

(4) A → letra A

(5) A → dígito

(6) A → dígito A

}

Gramática de tipo 3 o regular: ejemploGramática de tipo 3 o regular: ejemploGramática de tipo 3 o regular: ejemploGramática de tipo 3 o regular: ejemploP 2 = {

(1) S → letraletraletraletra

(2) S → _

(3) S → letra letra letra letra A

(4) S → _ A


4444

(4) S → _ A

(5) A → letraletraletraletra

(6) A → letra letra letra letra A

(7) A → dígitodígitodígitodígito

(8) A → dígitodígitodígitodígitoA

(9) A → _

(10) A → _ A

}

Gramática lineal por la derecha: ejemploGramática lineal por la derecha: ejemploGramática lineal por la derecha: ejemploGramática lineal por la derecha: ejemplo

P 3 = {

(1) S → bbbb A

(2) A → a a a a aaaa A

(3) A → bbbb


5555

(3) A → bbbb

(4) A → εεεε}

Gramática lineal por la derecha: ejemploGramática lineal por la derecha: ejemploGramática lineal por la derecha: ejemploGramática lineal por la derecha: ejemplo

P 4 = {

(1) S → a b aa b aa b aa b a A

(2) A → a aa aa aa a B

(3) A → a ba ba ba b


6666

(3) A → a ba ba ba b

(4) A → bbbb

(5) B → a ba ba ba b B

(6) B → εεεε}

Obtención de una gramática regular a partir Obtención de una gramática regular a partir Obtención de una gramática regular a partir Obtención de una gramática regular a partir

de la gramática lineal por la derecha P de la gramática lineal por la derecha P de la gramática lineal por la derecha P de la gramática lineal por la derecha P 4444

1. Reglas generadas por la regla (1) S → a b aa b aa b aa b a A

S → aaaa B 1B → bbbb B


7777

B 1 → bbbb B2

B 2 → aaaa A

2. Reglas generadas por la regla (2) A → a aa aa aa a B

A → aaaa B 3B 3 → aaaa B


de la gramática lineal por la derecha P de la gramática lineal por la derecha P de la gramática lineal por la derecha P de la gramática lineal por la derecha P 4 4 4 4 (continuación)(continuación)(continuación)(continuación)

3. Reglas generadas por la regla (3) A → a ba ba ba b

A → aaaa C 1C → bbbb


8888

C 1 → bbbb

4. Reglas generadas por la regla (5) B → a ba ba ba b B

B → aaaa B 4B 4 → bbbb B

5. Las reglas (4) y (6) no requieren ninguna transformación.


de la gramática lineal por la derecha P de la gramática lineal por la derecha P de la gramática lineal por la derecha P de la gramática lineal por la derecha P 4 4 4 4 (continuación)(continuación)(continuación)(continuación)El conjunto de reglas de producción que se ha obtenido esEl conjunto de reglas de producción que se ha obtenido esEl conjunto de reglas de producción que se ha obtenido esEl conjunto de reglas de producción que se ha obtenido es

P’ 4 = {

S → aaaa B 1A → aaaa B 3 | a C 1 | b


9999

A → aaaa B 3 | a C 1 | b

B → aaaa B 4 | εB 1 → bbbb B 2B 2 → aaaa A

B 3 → aaaa B

B 4 → bbbb B

C 1 → bbbb

}

Gramática regular con el símbolo inicial SGramática regular con el símbolo inicial SGramática regular con el símbolo inicial SGramática regular con el símbolo inicial S

en la parte derecha de las reglas en la parte derecha de las reglas en la parte derecha de las reglas en la parte derecha de las reglas

P 5 = {

(1) S → bbbb S

(2) S → aaaa A


10101010

(2) S → aaaa A

(3) A → aaaa S

(4) A → aaaa

}

Gramática regular con producciones épsilonGramática regular con producciones épsilonGramática regular con producciones épsilonGramática regular con producciones épsilon

P 6 = {

S → aaaa B | bbbb A | εεεεA → aaaa A | bbbb B | εεεεB → bbbb | εεεε


11111111

B → bbbb | εεεε}

Gramáticas regulares utilizadas en los ejemplos de operaciones Gramáticas regulares utilizadas en los ejemplos de operaciones Gramáticas regulares utilizadas en los ejemplos de operaciones Gramáticas regulares utilizadas en los ejemplos de operaciones

P 7 = {

S 1 → aaaa | aaaa A | aaaa B

A → aaaa | aaaa A | bbbb B

B → bbbb | bbbb B

}

∧


12121212

}

L(G 7 ) = {aaaa i bbbb j |i > 0 ∧ j ≥ 0}

P 8 = {

S 2 → aaaa A

A → bbbb | bbbb B

B → aaaa A

}

L(G 7 ) = {(abababab) i |i > 0}

UNIVERSIDAD DE CÓRDOBAUNIVERSIDAD DE CÓRDOBAUNIVERSIDAD DE CÓRDOBAUNIVERSIDAD DE CÓRDOBAESCUELA POLITÉCNICA SUPERIORESCUELA POLITÉCNICA SUPERIORESCUELA POLITÉCNICA SUPERIORESCUELA POLITÉCNICA SUPERIOR

DEPARTAMENTO DE INFORMÁTICA Y ANÁLISIS NUMÉRICODEPARTAMENTO DE INFORMÁTICA Y ANÁLISIS NUMÉRICODEPARTAMENTO DE INFORMÁTICA Y ANÁLISIS NUMÉRICODEPARTAMENTO DE INFORMÁTICA Y ANÁLISIS NUMÉRICO

INGENIERÍA TÉCNICA EN INFORMÁTICA DE SISTEMASINGENIERÍA TÉCNICA EN INFORMÁTICA DE SISTEMASINGENIERÍA TÉCNICA EN INFORMÁTICA DE SISTEMASINGENIERÍA TÉCNICA EN INFORMÁTICA DE SISTEMAS

SEGUNDO CURSO, SEGUNDO CUATRIMESTRESEGUNDO CURSO, SEGUNDO CUATRIMESTRESEGUNDO CURSO, SEGUNDO CUATRIMESTRESEGUNDO CURSO, SEGUNDO CUATRIMESTRE

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALESTEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES

Tema 4.Tema 4.Tema 4.Tema 4.Tema 4.Tema 4.Tema 4.Tema 4.-------- GramáticasGramáticasGramáticasGramáticasGramáticasGramáticasGramáticasGramáticas regularesregularesregularesregularesregularesregularesregularesregulares

tema 4.tema 4.- --- gramáticas regularesgramáticas regulares · 2019-07-18 · obtención de una...

Documents