Lenguajes Formales rafael ramirez [email protected] Ocata 320

Conceptos centrales „

„

„

„

„

Un alfabeto es un conjunto (finito y no vacio) de símbolos. Σ={0,1} Σ={a,b,…,z} Una cadena (a veces llamada palabra) es una sequencia (finita) de símbolos de algun alfabeto. 01101 es una cadena del alfabeto Σ={0,1} La cadena vacia є es la cadena con cero símbolos La longitud de una cadena es el número de símbolos que contiene | 01101 | = 5 |є|=0 La potencia k de un alfabeto es el conjunto de cadenas con longitud k si Σ={0,1}, Σ1 ={0,1}, Σ2 ={00,01,10,11} El conjunto de todas las cadenas sobre un alfabeto se denota Σ* 2

Conceptos centrales „

xy denota la concatenacion de las cadenas x e y si x=barce, y=lona entonces xy=barcelona

„

Un lenguaje es un conjunto de cadenas escogidas de algun Σ* el conjunto de cadenas con mismo numero de 0s que de 1s = {є,01,10,0011,0101,1001,…} = {w | w consiste de el mismo numero de 0s que de 1s}

3

Gramáticas formales Una gramática formal consiste en:

„

„ „ „ „

„

„

Un alfabeto Σ Un conjunto de símbolos terminales T ⊆ Σ Un conjunto de reglas de produccion Un símbolo inicial El lenguaje generado por una gramática G (que se denota por L(G) ) es el conjunto de cadenas sobre Σ que puede ser producido por las reglas de produccion empezado con el simbolo inicial. A Σ − T se le llama el conjunto de simbolos no terminales 4

Ejemplo 1 Alfabeto:

Σ = {0,1,S}

Conjunto de simbolos terminales: (conjunto de simbolos no terminales:

T = {0,1} Σ − T = {S} )

„

Reglas de produccion:

S→є S → 0S1

„

Simbolo inicial:

S

„

„

Que lenguaje L(G) genera esta gramatica G? 5

Ejemplo 2 „

„

Alfabeto: Σ = conjunto de palabras en español y algunos simbolos no terminales Σ = {el, la, niño, niña, corre, come, tarta, Oracion, Sujeto, Predicado, Verbo, Articulo, Sustantivo} Conjunto de simbolos terminales: T = {el, la, niño, niña, corre, come, tarta}

„

Reglas de produccion:

„

Simbolo inicial:

Oracion → Sujeto Predicado Sujeto → Articulo Sustantivo Predicado → Verbo Articulo Sustantivo Verbo → corre | come Articulo → el | la Sustantivo → niño | niña | tarta

Oracion 6

Ejemplo 2 „

Operador de remplazo ⇒ : remplaza cualquier no terminal en el lado izquierdo de cualquier produccion por el lado derecho de la produccion Oracion ⇒ Sujeto Predicado ⇒ Articulo Sustantivo Predicado ⇒ el Sustantivo Predicado ... ⇒ el niño come la tarta

„

Regla 1 Regla 2 Regla 5

A partir de Oracion tambien podemos derivar ⇒ el pastel come el niño La sintaxis no implica semantica correcta 7

Derivaciones „

„ „ „

Una derivacion es una secuencia de formas sentenciales empezando con el símbolo inicial.

Gramatica: B → 0B | 1B | 0 | 1 Derivacion: B ⇒ 0B ⇒ 01B ⇒ 010 Cada paso de derivation es la aplicacion de una regla de produccion.

8

Arboles de parse „

„

„

„ „ „

Un arbol de parse es una estructura sintactica herárquica Los nodos internos denotan no terminales Las hojas (nodos externos) denotan terminales. Gramatica: B → 0B | 1B | 0 | 1 Derivacion: B ⇒ 0B ⇒ 01B ⇒ 010 A partir de la derivacion podemos obtener el arbol de parse.

9

Derivaciones – arbol de parse „

„ „ „

„

Las derivaciones no necesariamente son unicas S → SS | (S) | () S ⇒ SS ⇒(S)S ⇒(())S ⇒(())() S ⇒ SS ⇒ S() ⇒(S)() ⇒(())() En este caso tenemos diferentes derivaciones pero obtenemos el mismo arbol de parse

10

Derivaciones – arbol de parse Pero a partir de algunas gramaticas podemos obtener 2 arboles de parse diferentes para la misma cadena: ()()(). Cada arbol de parse corresponde a una unica derivacion: S ⇒ SS ⇒ SSS ⇒()SS ⇒()()S ⇒()()()

Una gramatica es ambigua si alguna cadena tiene 2 arboles de parse distintos. Para entender la semantica de un lenguaje nos gustaria tener gramaticas no ambiguas 11

Pregunta „

Es esta gramática ambigua? (intenta construir dos arboles de parse diferentes para una misma cadena) E E E N

→E+E →E*E →N →1|2|3|4

12

Respuesta: E E E N

considera la cadena 2 + 3 * 4

→E+E →E*E →N →1|2|3|4

E

E E N 2

+ N 3

E *

E I

N 4

2

+

*

E

I

I

3

4 13

Para desambiguarla „

(Caso 1) + con precedencia sobre * E → E2 | E2 * E E2 → N | N + E2

1+2*3

1

(1+2)*3

+

*



2

3

14

Herarquía de Chomsky „

Gramaticas Regulares: (tipo 3) „ „

„

„

subclase de las que hemos estado viendo (tipo 2) Las reglas estan restringidas a: A → t N | t donde: N = no terminal, t = terminal Ejemplo: B → 0 B | 1 B | 0 | 1

Gramaticas libres de contexto: (tipo 2) „

Las que hemos estado viendo

„

Las reglas estan restringidas a: A → α

„

donde: α = cadena de 0 o mas terminales y no terminales Ejemplo: S → SS | (S) | ()

15

Herarquía de Chomsky (cont) „

Gramaticas sensibles al contexto: (tipo 1) „ „

„

Reglas: α → β donde | α | ≤ | β | e.d. long. de α ≤ long. de β,

Gramaticas irrestringidas: (tipo 0) „

Reglas: α → β. Sin restricciones en α y β. 16

DERIVACION Grammar

Tree

V = {…}

Cadena 19a0c6duw

Σ = {…} R = {…} S = {…}

PARSING

Tree 17

Top Down parsing „

Gramática →

N

→ → Real Int-part → Fraction → Digit → Es “12.34” aceptado inicial? Int

„

Top-Down Parse

=> => => =>

1

Int | Real Digit | Digit Int Int-part . Fraction Digit | Int-part Digit Digit | Digit Fraction 0|1|2|3|4|5|6|7|8|9

por la gramática con N como símbolo

(Try first choice) (Try first choice) (Backtrack : “2.34” not parsed)

18

Top Down parsing „

Gramática →

N

→ → Real Int-part → Fraction → Digit → Es “12.34” aceptado inicial? Int

„

Top-Down Parse

=> => => => => =>

Int | Real Digit | Digit Int Int-part . Fraction Digit | Int-part Digit Digit | Digit Fraction 0|1|2|3|4|5|6|7|8|9

por la gramática con N como símbolo

1 1 12

(Try first choice) (Try second choice) (Try first choice) (Backtrack: “.34” not parsed) 19

Top Down parsing „

Gramática →

N

→ → Real Int-part → Fraction → Digit → Es “12.34” aceptado inicial? Int

„

Top-Down Parse

=> => => => =>

Int | Real Digit | Digit Int Int-part . Fraction Digit | Int-part Digit Digit | Digit Fraction 0|1|2|3|4|5|6|7|8|9

por la gramática con N como símbolo

. … 12.34

(Try second choice) (success!)

20

Bottom-up parsing „

Gramática →

N

→ → Real Int-part → Fraction → Digit → Es “12.34” aceptado inicial? Int

„

Bottom-Up Parse

=> => => =>

Int | Real Digit | Digit Int Int-part . Fraction Digit | Int-part Digit Digit | Digit Fraction 0|1|2|3|4|5|6|7|8|9

por la gramática con N como símbolo

12.34 2.34 2.34 2.34

(Backtrack)

21

Bottom-up parsing „

Gramática →

N

→ → Real Int-part → Fraction → Digit → Es “12.34” aceptado inicial? Int

„

Bottom-Up Parse

=> => => => => =>

Int | Real Digit | Digit Int Int-part . Fraction Digit | Int-part Digit Digit | Digit Fraction 0|1|2|3|4|5|6|7|8|9

por la gramática con N como símbolo

12.34 2.34 .34 .34 .34 .34

(Backtrack) 22

Bottom-up parsing „

Gramática →

N

→ → Real Int-part → Fraction → Digit → Es “12.34” aceptado inicial? Int

„

Bottom-Up Parse

=> => => => => => =>

Int | Real Digit | Digit Int Int-part . Fraction Digit | Int-part Digit Digit | Digit Fraction 0|1|2|3|4|5|6|7|8|9

por la gramática con N como símbolo

12.34 … .34 … .

(Success!) 23

Automatas Automata Finito Una manera importante de describir los simples pero muy utiles lenguajes

regulares

• • • •

Un grafo con un numero finito nodos, llamados estados Los arcos estan etiquetados con uno o mas símbolos de algun alfabeto Un estado es designado el estado inicial Algunos estados son finales

El lenguaje del AF es el conjunto de cadenas que contienen los simbolos que en los arcos en un camino desde el estado inicial a algun estado final.

24

Automatas: ejemplo

inicio

h

h

o

ho

l

hol

a

hola

25

Automata Finito

(formal)

Un automata finito M consiste en: 1. un conjunto finito QM de simbolos (los elementos de QM se llaman los estados de M); 2. un elemento sM de QM (sM se llama estado inicial de M); 3. un subconjunt AM de QM (los elementos de AM se llaman estados finales o “accepting states” de M); 4. a subconjunto finito TM de { (q, x, r) | q, r en QM y x es una cadena} (los elementos de TM se llaman transiciones de M).

26

Automata Finito Ejemplo 1. QM = {A,B,C}; 2. sM = A; 3. AM = {A,C}; 4. TM = {(A, 1,A), (B, 11,B), (C, 111, C), (A, 0,B), (A, 2,B), (A, 0, C), (A, 2, C), (B, 0, C), (B, 2, C)}.

27

Definicion: autómata „

Un autómata finito consiste en: „

Un conjunto finito de estados

„

Un estado inicial

„

Un conjunto de estados finales

„

Una funcion de transicion

28

Automata Finito Ejemplo 1. 2. 3. 4.

QM = {A,B,C}; sM = A; AM = {A,C}; TM = {(A, 1,A), (B, 11,B), (C, 111, C), (A, 0,B), (A, 2,B), (A, 0, C), (A, 2, C), (B, 0, C), (B, 2, C)}.

Dibuja la representacion grafica de M

29

Automata Finito Ejemplo 1. 2. 3. 4.

QM = {A,B,C}; sM = A; AM = {A,C}; TM = {(A, 1,A), (B, 11,B), (C, 111, C), (A, 0,B), (A, 2,B), (A, 0, C), (A, 2, C), (B, 0, C), (B, 2, C)}.

30

Automata Finito Los automatas finitos pueden ser determinaistas o nodeterministicas. toman cadenas como entradas. Cuando un automata ejecuta con una entrada dada, empieza en su estado inicial.

31

Automata Finito Si, 1. 2. 3.

despues de un numero de pasos, el automata esta en un estado p, la entrada restante empieza con x, y hay una transicion (p, x, q) en el automata,

Entonces el automata puede leer x de su entrada y cambiar al estado q. Si (p, z, r) es una transicion del automata, y la entrada restante empieza con z, entonces se podria consumir z y cambiar al estado r, etc.

32

Automata Finito Si al menos una sequencia de ejecucion consume toda la entrada y llega un estado final, se dice que la entrada es aceptada por el automata. De lo contrario se dice que es rechazada. El significado del automata es el lenguaje que consiste en todas las cadenas que acepta.

33

Lenguaje de un autómata „

„

El lenguaje de un autómata finito (AF) es el conjunto de cadenas que el AF acepta: Cual es el lenguage del siguiente automata?

inicio

0 q0

0

q1

1 1

q2

34

Lenguaje de un autómata „

„

„

El lenguaje de un autómata finito (AF) es el conjunto de cadenas que el AF acepta: Ej. Considera el siguiente lenguaje: L= { w | w es de la forma XY para algunas cadenas X e Y tal que X consiste en un numero impar de 0´s e Y cualquier numero de 1´s} L es el lenguaje del siguiente autómata:

inicio

0 q0

0

q1

1 1

q2 35

Autómata finito nodeterminista „

„

„

Permite a un AF (determinista) tener cero o mas estados siguientes para un par estado-simbolo. Herramienta importante para diseñar procesadores de lenguajes, p.e. analizadores lexicos. Pero son imaginarios en el sentido de que tienen que ser implementados deterministamente.

Ejemplo: AFN que acepta cadenas de simbols en {1,2,3} tales que el ultimo simbolo ya ha aparecido antes en la cadena.

36

Ejemplo

Cual es el lenguage del automata?

37

Ejemplo

Cual es el lenguage del automata?

38

Ejemplo

Cual es el lenguage del automata?

Ejercicio: el languaje de todas las cadenas sobre {a,b} Con un numer par de a’s (encuentra el autómata). 39

Ejemplo

Que cadena no esta en el lenguaje del automata? Cual es el lenguage del automata? Kleene’s Thm: Un lenguaje L sobre Σ es regular ssi existe un automata finito que acepta L. 40

Pushdown Automata

Generators vs. Recognizers „

For Regular Languages: „ „

„

regular expressions are generators FAs are recognizers

For Context-free Languages „ „

CFGs are generators Pushdown Automata (PDAs) are recognizers

42

PDA vs. FA „ „

Add a stack Each transition can specify optional push and pop operations „ „

using an independent alphabet use Λ (or e) to ignore stack operations „

„

a,e/A means with input ‘a’, pop nothing, push an ‘A’

Usually require an empty stack to accept „

in addition to being in an “accept” state

43

Example:

-+

n n ab

a,e/A

X

a,e/A

b, A/e

+Y b, A/e

44

Example: „ „

Every input ‘a’ pushes a ‘A’ on the stack Every input ‘b’ pops an ‘A’ off the stack „

„

n n ab

if any other character appears, reject

At end of input, the stack should be empty „

else the count was off, and we should reject 45

Example: PalindromeX „ „ „

Accepts strings of the form wcwR Pops the first half onto the stack middle delimiter to know when to start comparing in reverse

46

Palindrome

a,e/a b,e/b

a,a/e c,e/e

+ b,b/e

47

Example: EvenPalindrome

a,e/a b,e/b

a,a/e e,e/e

+ b,b/e

No delimiter

48

Non-determinism „ „

„

Can have e-moves Can have multiple moves for the same input As long as an acceptable path exists, the machine accepts the input

49

CFG => PDA „

Has two states: „

„

„

start, accepting

Have an empty move from the start state to the accepting state that pushes the start non-terminal Cycle on the accepting state: „

„

empty moves that replace variables with each of their rules moves that consume each terminal 50

CFG => PDA Example S => e | (S) | SS

e,S/(S) -

e,e/S

e,S/SS +

(,(/e

),)/e

e,S/e

51

Derive (()) „

Using CFG (do a leftmost-derivation): „

„

S => (S) =>((S)) => (())

PDA (non-deterministically) „

do by hand, showing stack at each step

52

A DPDA for (…)

(,e/R

-+

),R/e

Exercise: accept (( )( ))

53

CFG vs. PDA „

Any CFG can be represented by a PDA „

some CFGs require non-determinism „

„

„

unlike NFA’s => FAs => regular expressions

i.e., the languages accepted by DPDAs form a subset of those accepted by NPDAs

Any PDA has a corresponding CFG „

Lots of work to find!!!

54