1 Tomado de Sudkamp: Languages and Machines Cap. 6.Autómatas finitos Tomado de Sudkamp: Languages and Machines Cap. 6.

2 Autómatas Finitos (determinísticos)M=(,Q,,q0,F) Alfabeto Estados finales Estado inicial Conjunto de estados Función de transición  a b q0 q2 q1 a b Q q0 q1 q2 q1 q2 q0

3 Funcionamiento del autómataM=(,Q,,q0,F) Palabras que contienen a ab q0 q2 q1 a b *(aab,q1)=  (*(aa,q1),b)= (  (*(a,q1),a),b)=  ((  (*(,q1),a),a),b)=  ((  (q1,a),a),b)=  (( q1,a),b)=  ( q1,b)= q2 [q1,aab][q1,ab][q1,b][q2,]

4 Ejemplos q1 q2 q3 q0 q1 q0 q2 Palabras que contienen exactamente 2 a’sPalabras que contienen exactamente 3k b’s q0 a b q1 q3 q2 Lenguaje representado por la expresión aa*b

5 Autómatas finitos no determinísticosq1 q0 q2 q1 q0 q2 q1 q2 q0 q1 q2 q3 q0

6 Autómatas finitos no determinísticosPalabras que empiezan por ab y terminan con ba q1 q2 q0 q4 q3 q5 q6 a(ba wb(awb)*ba)

7 Autómatas finitos no determinísticosM=(,Q,,q0,F) q1 q2 q0 q4 q3 q q q q q4 a q  q q  b  q q2,q  

8 Autómatas finitos no determinísticosM=(,Q,,q0,F) qi qk qj w u

9 Autómatas FND M=(,Q,,q0,F)

10 Ejemplos AFND

11 Ejemplos AFND (6.4.6) {, ab, aabb, aaabbb} ?

12 Autómatas con transiciones  -AFNM=(,Q,,q0,F) q12 a,b q10 b q11 q21 a b q20 q12 a,b q10 b q11 q0  q21 a,b a b q20

13 Clausura con -AFN Si M1 y M2 son -AFN existen -AFN tales que: M1 M2

14 Clausura con -AFN Si M1 y M2 son -AFN existen -AFN tales que: q11

15 Concluimos…. Toda expresión regular tiene al menos un correspondiente -AFND que acepta exactamente las palabras correspondientes a la expresión.

16 Eliminando el indeterminismoLa clausura Lambda, para cada estado qi, se construye recursivamente así: BASE: Paso recursivo La función de transición de entradas t para un -AFND se define así:

17 Ejemplo 6.6.1  q0 q1 q2 a q0,q1,q2   b   q2 c  q1    q2  q2t q q q2 a q0,q1,q   b  q q2 c  q1,q 

18 Algoritmo 6.6.3 Construction of DM, a DFA Equivalent to NFA- M Input:an NFA- M=(Q,,,q0,F). input transition fuction t of M 1. initialize Q’ to -Cl(q0) 2. repeat until done 2.1 if there is a node XQ’ and a symbol a with no arc leaving X labeled a then 2.1.1 let 2.1.2 if then set 2.1.3 add an arc from X to Y labeled a else done:=true 3. The set of accepting states of DM is F’={XQ’| X contiene algún elemento de F}

19 Ejemplo q2 q0 q1 t q0 q1 q2 a q0,q1,q2   b  q2 q2 c  q1,q2  b a a,b,c q0  b,c a q0,q1,q2 a a,c a b q2 b b q1,q2 c c

20 Grafos de expresiones q1 q0 q2 q2 q0 q0 (a*ba*ba*ba*)* a*ba*ba*ba*

21 Eliminar el estado intermedio ik j wji wik wik j k wji i j wji k wik wii (wii)*wik j k wji i debe ser diferente de j y de k pero puede ser j=k

22 Situaciones finales w W* w1 w3 w4 w2 w1* w2(w3  w4w1*w2)*

23 Grafos de expresiones q1 q0 q2 ba*b q2 q0 (a*ba*b)(a*  ba*ba*b)*

24 Expresión de un AFND (ab)*bb (ab)* (ab)*aa (ab)*

25 Gramática regular para un AFNDq1 q0 q2 S → aS| bB|  B → aB| bC C → aC| bS

26 Gramática para un AFND (cont)q1 q2 q0 q4 q3 q5 q6 S → aB B → bC| bD C → aC| bC | bE S → aB D → aF B → bC| bD S → aB E → aG C → aC| bC | bE B → bC| ba F →  D → a C → aC| bC | ba G →  E → a

27 AFND para un gramática regularPalabras sobre {a,b,c} que contiene al menos una c pero no contienen cc. S → aS| bS |cA q1 q0 a,b c A → aS| bS| 

28 Lenguajes regulares Expresiones Regulares No son LR: AFD AFNDGramáticas Regulares

29 Pre-Lema de bombeo Sea w1,w2,w3,w4,…. y v1,v2,v3,v4,… sucesiones infinitas de palabras. Si L es un lenguajes tal que wivj pertenece a L si y sólo sí i=j. Entonces L no es regular. Si existiera un autómata finito de k estados existen i

30 Aplicación No son regulares:

31 Lema de Bombeo q1 q0 qi qk Si |z|>k existen u,v y w tales que|uv|0 y uvnw para todo n está en L Un autómata de k estados si acepta una palabra de longitud mayor que k acepta infinitas palabras Un autómata de k estados acepta infinitas palabras si y solo si acepta alguna  tal que k< || < 2k

32 Aplicación Las palabras cuya longitud es un cuadrado perfecto no forman un lenguaje regular. Supóngase que un autómata de k estados acepta tal lenguaje, tómese entonces una palabra z con longitud k2 , entonces z=uvw con |uv|k o sea |v|k y además uv2w es aceptada por el autómata, Pero |uv2w| no puede ser cuadrado perfecto pues: |uv2w|= |uvw|+|v|=k2+|v| k2+k<(k+1)2 Entre k2 y (k+1)2 no hay ningún cuadrado perfecto !

33 Propiedades de clausuraConjuntos finitos de palabras forman lenguajes regulares Unión de dos Concatenación de dos ...lenguajes regulares, es un lenguaje regular Intersección de dos Complemento de * de