Depende del contexto

2

3

4

Autómata de pila

Reflexiones sobre el determinismo en AP

5

1

Autómata de pila

Es una tupla (Q,Σ,Γ,q₀,Z₀,A,δ):

• Q un conjunto de estados finitos
• Σ es un alfabeto de símbolos terminales
• Γ es un alfabeto de la pila
• q₀ es el estado inicial
• Z₀ es el símbolo inicial de la pila
• ẟ función de transición δ:QX(Σ∪{𝜺})XΓ→QXΓ*

​

​

6

AFND-𝜺 + PILA

AFND-𝜺 + PILA

Es no determinista

7

AP determinístico

Es un AP, pero además cumple

​

• Sólo hay una transición δ(q,a,x) por estado
• Si existe δ(q,ε,x), entonces no existe ninguna de otro tipo δ(q,a,x)

8

wmw^r

9

ww^r

10

w=w^r

11

Resumen

• w=w^r no determinístico
• ww^r no determinístico
• wmw^r determinístico

​

12

Gramáticas

• w=w^r, P→aPa|bPb|a|b|ϵ
• ww^r, P→aPa|bPb|aa|bb
• wmw^r, aPa|bPb|m

​

​

Todas son no ambiguas

13

Ambigüedad y determinismo

Lenguaje inherentemente ambigua

• no-ambigua → determinista o no-determinista
• ambigua → no determinista
• determinista → no-ambigua
• no-determinista → ambigua o no ambigua

​

​

14

Simulaciones

De AP a GLC y de GLC a AP

15

2

G como AP

Dado una G=(V,Σ,P,S) se puede generar (Q,Σ,Γ,q0,Z0,A,δ) como

• Q={q₀,q₁,q₂}
• Γ=V U Σ U {Z₀}
• A={q₃}

16

G como AP

Con las transiciones con esta forma, para iniciales

• δ(q₀,𝜺,Z₀) ={(q₁,SZ₀})}
• δ(q₁,𝜺,Z₀) ={(q₂,Z₀})}

​

Para reglas de producciones

• δ(q₁,𝜺,A) ={(q₁,α}) |A→α}
• δ(q₁,a,a) ={(q₁,𝜺})}

17

De forma gráfica

18

Ejemplo: w=w^r

P→aPa|bPb|a|b|ϵ

19

¿De AP a GLC?

20

“

¿Cúal es su GLC?

21

Caso general: AP a GLC

​

Las transiciones a,A/α se transforma A→aα

22

Caso específicos: AP a GLC

• Pushes
• Z₀→aAZ₀
• A→aAA

​

• Pop
• A→a

• Transiciones
• Z₀→mZ₀
• A→mA

​

• Termino
• Z₀→𝜺

23

¿Cúal es su GLC?

24

Z₀→aAZ₀

Z₀→bBZ₀

A→aAA

B→aAB

A→bBA

B→bBB

Z₀→mZ₀

A→mA

B→mB

A→a

B→b

Z₀→ϵ

Derivar: abbmbba

25

Z₀→aAZ₀

Z₀→bBZ₀

A→aAA

B→aAB

A→bBA

B→bBB

Z₀→mZ₀

A→mA

B→mB

A→a

B→b

Z₀→ϵ

26

Completo

27

Lema de bombeo

La venganza

28

Lema de bombeo

Una w de un lenguaje regular podrá ser dividida w en uvwxy, con vx con longitud positiva, y se podrá identificar una longitud p entonces se puede bombear u y x para generar cadenas del lenguaje

29

Procedimiento

• Proponer lenguaje L
• Escoger p
• Proponer cadena w que dependa de p
• Particionar w en uvwxy tal que
• |vwx| > p
• |vx| > 0
• Entonces uvⁱwxⁱy ∈ L

30

Procedimiento

• Proponer lenguaje L: aⁿbⁿcⁿ
• Escoger p
• Proponer cadena w que dependa de a^pb^pc^p
• Particionar w en uvwxy tal que
• |vwx| > p
• |vx| > 0

�Varios casos

31

Procedimiento aⁿbⁿcⁿ

• Casos
• vwx son aes: aⁱaⁱbⁿcⁿ
• vwx son aes y bes: aⁱbⁱcⁿ
• vwx son bes: aⁿbⁱbⁱcⁿ
• vwx son bes y ces: aⁿbⁱcⁱ
• vwx son ces: aⁿbⁿcⁱcⁱ

​

• Por lo tanto no es LLC

32

Lenguaje dependiente del contexto

Depende de

33

34

35

36

37

38

39

Gramáticas dependientes de contexto

Son una tupla G=(V,Σ,P,S), donde:

• V es otro alfabeto que denominamos símbolos no terminales (generalmente en mayúsculas)
• Σ es un alfabeto que denominamos símbolos terminales
• P es conjunto de reglas con la forma 𝛾A𝛽→𝛾𝛼𝛽 donde 𝛾,𝛽 ∈(Σ∪V)* , α∈(Σ∪V)⁺ y A∈V
• S∈V que denominamos símbolo inicial

​

40

Ejemplo

41

Derivación

42

S

⇒ aSBC

⇒aaSBCBC

⇒aaabCBCBC

⇒aaabWBCBC

⇒aaabWXCBC

⇒aaabBXCBC

⇒aaabBCCBC

⇒aaabBCWBC

⇒aaabBCWXC

⇒aaabBCBXC

⇒aaabBCBCC

⇒aaabBWBCC

⇒aaabBWXCC

⇒aaabBBCCC

⇒aaabbBCCC

⇒aaabbbCCC

⇒aaabbbcCC

⇒aaabbbccC

⇒aaabbbccc

​

Ejemplo

43

44

45

¿?

Gracias

Alguna pregunta ?

​

​

• @ivanvladimir
• ivanvladimir@turing.iimas.unam.mx

46

Resumen

Determinismo no determismo

De AP a GLC

De GLC a AP

Lema de bombeo GLC

Gramáticas dependientes del contexto

Derivaciones

​

​

​

Esta obra está bajo una Licencia Creative Commons Atribución 4.0 Internacional.

​