contenido - cs.uns.edu.arcs.uns.edu.ar/~td/lfya2011/downloads/teoricas/automatas finitos... ·...
Post on 20-Sep-2018
228 Views
Preview:
TRANSCRIPT
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómatas finitos y lenguajes regulares
CONTENIDOReconocedores [HMU2.1].
Traductores [C8]. Diagramas de Estado [HMU2.1]. Equivalencia entre AF deterministas y no deterministas[HMU2.2-2.3]. Expresiones regulares[HMU3]. Propiedades de lenguajes regulares [HMU4]. Relación entre gramáticas regulares, lenguajes regulares y autómatas finitos [A1-2].
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
bibliografía
HOPCROFT, JOHN E., MOTWANI, RAJEEV Y ULLMAN, JEFFREY D. “Introducción a la Teoría de Autómatas, Lenguajes y Computación”. Segunda Edición. AddisonWesley. 2002.
COHEN, DANIEL I.A. “Introduction toComputer Theory”, Second Edition, John Wiley & Sons, Inc. 1997.
AUGUSTO, JUAN CARLOS . “Fundamentos de Ciencias de la Computación” – Notas de Curso. Universidad Nacional del Sur, Argentina. 2002.
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómatas finitos reconocedores
S0 S1
S2
0 0
0
11
1
Autómata FinitoReconocedor
Reconoce el lenguaje sobre Σ={0,1} con un número múltiplo de 3 de 1’s
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómatas finitos traductores
S0/1 S1/0
S2/0
0 0
0
11
1
Autómata FinitoDe Moore
Emite 1 mientras el número de 1’s leídos hasta elmomento sea múltiplo de 3, de lo contrario emite 0
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómatas finitos traductores
S0 S1
S2
0/0 0/0
0/0
1/01/1
1/0
Autómata FinitoDe Mealy
Emite 1 cuando el número de 1’s leídos se vuelve múltiplo de 3 (≠ 0), de lo contrario emite 0
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómatas finitos
Un autómata finito es un modelo que captura las características de una computadora.
Veremos dos tipos de autómatas finitosAutómatas Finitos Reconocedores (AFR)Son capaces de reconocer lenguajes regulares
(exactamente el mismo lenguaje generado por gramáticas de tipo 3)
Autómatas Finitos TraductoresToman una entrada y la traducen en una salida
Autómatas de Moore: las salidas van asociadas a los estadosAutómatas de Mealy: las salidas van asociadas a las transiciones
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómata finito reconocedor
Un autómata finito reconocedor (AFR) es una quíntupla
M = (S, Σ, δ, s0, F),donde:S es un conjunto finito de estados, S≠∅Σ es el alfabeto de entradaδ: S x Σ → S es la función de transicións0 es el estado inicial, s0 ∈ S.F es el conjunto de estados finales oaceptadores (F ⊆ S)
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómata finito reconocedor
EjemploM = (S, Σ, δ, s0, F),S = {s0, s1, s2}, Σ = {0,1}, F ={s0}
S0 S1
S2
0 0
0
11
1
s0s2s2
s2s1s1
s1s0s0
10δ
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómata finito reconocedor
EjemploDar un autómata finito reconocedor para
el lenguaje de las cadenas definidas sobre el alfabeto Σ={a,b} tales que empiezan con a.
M = (S, Σ, δ, s0, F),S = {s0, s1, s2}, Σ = {a,b}, F ={s1}
s2s2s2
s1s1s1
s2s1s0
baδ
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómata finito reconocedor
Ejercicios1. Dar un AFR para el lenguaje definido
sobre el alfabeto Σ={0,1,2,3,4,5,6,7,8,9} tal que reconozca los números pares.
2. Dar un AFR para el lenguaje definido sobre el alfabeto Σ ={a,b} cuyas cadenas tienen la letra b como segundo símbolo.
3. Dar un AFR para el lenguaje definido sobre el alfabeto Σ ={a,b} cuya longitud es par pero no divisible por 6.
4. Dar un AFR para el lenguaje definido sobre el alfabeto Σ={0,1} tal que las cadenas tienen un número par de 0’s y número par de 1’s.
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
generalización de la función de transición δ
Definimos δ*: S x Σ* → S como sigue:δ*(q, λ)=qδ*(q, aw)= δ*(δ(q, a),w)donde a ∈ Σ y w ∈ Σ*
Una forma equivalente de definir δ*:δ*(q, λ)=qδ*(q, wa)= δ(δ*(q, w),a)
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
el lenguaje de un AFR
El lenguaje reconocido por el AFR M = (S, Σ, δ, s0, F), se denota L(M) y se define como:
L(M)={w| δ*(s0,w) ∈ F}Es decir, el lenguaje de M es el conjunto
de cadenas w tales que comenzando del estado inicial de M nos llevan a algún estado final.
Si L = L(M) para algún M, entonces L es regular.
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómata finito traductor de Moore
Un autómata finito traductor de Moore es una séxtupla
M = (S, Σ, Γ ,δ, s0, f0),donde:S es un conjunto finito de estados, S≠∅.Σ es el alfabeto de entrada.Γ es el alfabeto de salida.δ: S x Σ → S es la función de transicións0 es el estado inicial, s0 ∈ S.f0: S → Γ es la función de salida.
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómata finito traductor de Moore
EjemploM = (S, Σ, Γ ,δ, s0, f0),S = {s0, s1, s2}, Σ = {0,1}, Γ={0,1}
s0
s2
s1
1
0
0
1
f0
s2s2
s1s1
s0s0
0δ S0/1 S1/0
S2/0
0 0
0
11
1
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómata finito traductor de Moore
Ejercicio1.Dar un autómata finito traductor de
Moore que emita un 1 cada vez que se hayan leído la secuencia bbba.
2. Dar un autómata finito traductor de Moore que simule la función booleana AND.
3. Dar un autómata finito traductor de Moore que simule la función booleana OR.
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómata finito traductor de Mealy
Un autómata finito traductor de Mealy es una séxtupla
M = (S, Σ, Γ ,δ, s0, f0),donde:S es un conjunto finito de estados, S≠∅.Σ es el alfabeto de entrada.Γ es el alfabeto de salida.δ: S x Σ → S es la función de transicións0 es el estado inicial, s0 ∈ S.f0: S x Σ → Γ es la función de salida.
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómata finito traductor de Mealy
EjemploM = (S, Σ, Γ ,δ, s0, f0),S = {s0, s1, s2}, Σ = {0,1}, Γ={0,1}
s0/1s2/0s2
s2/0s1/0s1
s1/0s0/0s0
10δ/ f0S0 S1
S2
0/0 0/0
0/0
1/01/1
1/0
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómata finito traductor de Mealy
Ejercicio1. Convertir los autómatas de Moore de
los ejercicios previos a autómatas de Mealy.
2. Dar un autómata finito traductor de Mealy que realice suma binaria.
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómata finito no determinista
Un autómata finito reconocedor no determinista (AFRND) es una quíntupla
M = (S, Σ, δ, s0, F),donde:S es un conjunto finito de estados, S ≠∅.Σ es el alfabeto de entrada.δ: S x Σ → 2S es la función de transición.s0 es el estado inicial, s0 ∈ S.F es el conjunto de estados finales oaceptadores (F ⊆ S).
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómata finito no determinista
S0 S1
a,b a,b
a
Autómata FinitoReconocedor
No Determinista
EjemploM = (S, Σ, δ, s0, F),
S = {s0, s1}, Σ = {a, b}, F ={s1}
{s1}{s1}s1
{s0 }{s0,s1}s0
baδ
L(M) es el lenguajes de cadenas sobre Σ = {a, b}que contienen al menos una a
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómata finito no determinista con transiciones λ
Un autómata finito reconocedor no determinista con transiciones λ (AFRND-λ) es una quíntupla
M = (S, Σ, δ, s0, F),donde:S es un conjunto finito de estados, S ≠∅Σ es el alfabeto de entrada.δ: S x (Σ ∪ {λ}) → 2S es la función de
transición.s0 es el estado inicial, s0 ∈ S.F es el conjunto de estados finales oaceptadores (F ⊆ S).
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
autómata finito no determinista con transiciones λ
P0 I0
1 1
0
0
P1 I1
0 0
1
1
P0 I0
1 1
0
0
P1 I1
0 01
1
S0
λ
λ
Número impar de ceros
Número par de unosNúmero impar de ceros o
par de unos
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
generalización de la función de transición δ
Para AFRND Definimos δ*: S x Σ* → 2S
como sigue:δ*(q, λ)={q}δ*(q, wa)= {r1,r2,…,rm}donde δ*(q,w) = {p1,p2,…,pk} y
δ(pi,a) ={r1,r2,…,rm}Uk
i 1=
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
el lenguaje de un AFR
El lenguaje reconocido por el AFRND M = (S, Σ, δ, s0, F), se denota L(M) y se define como:
L(M)={w | δ*(s0,w) ∩ F ≠ ∅}Es decir, el lenguaje de M es el conjunto
de cadenas w tales que comenzando del estado inicial de M nos llevan a algún conjunto de estados que contenga al menos un estado final.
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
equivalencia entre AFR deterministas y no deterministas (tema a verse en clase práctica)
A partir de un AFRNDN = (S, Σ, δ, s0, F) obtenemos un AFR determinista D = (Sd, Σ, δd, {s0}, Fd)Sd = 2S
Fd es el conjunto de subconjuntos Q ∈Sd tal que Q ∩ F ≠ ∅Para cada conjunto Q ⊆ S y para cada símbolo a ∈ Σ
UQp∈
δd (Q,a)= δ(p,a)δd es una función de transición determinista
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
AFRND -> AFRD(tema a verse en clase práctica)
S0 S1
a,b a,b
a{S0} {S0,S1}
b a,b
a
∅ {S1}
a,b a,b
cadenas sobre Σ = {a,b} que contienen al menos una a.
AFRND
AFRD
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
AFRND -> AFRD(tema a verse en clase práctica)
EjemploM = (S, Σ, δ, s0, F),
S = {s0, s1}, Σ = {a,b}, F ={s1}
s1s1s1
s0{s0,s1}s0
baδ
M = (Sd, Σ, δd, {s0}, Fd)
Sd = {∅,s0, s1,{s0, s1}}, Σ = {a,b}, Fd ={{s1}, {s0, s1}}
{s0}{s0, s1}{s0}{s1}{s1}{s1}{s0,s1}{s0, s1}{s0, s1}
∅∅∅
baδd
AFRND
AFRD
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
AFRND -> AFRD(tema a verse en clase práctica)
EjercicioObtener el AFRD equivalente a los
dados a continuación
S0 S1
a,b
a
S0 S10
S2 S3
0,10 0
1)
2)
En lo que sigue usaremos AF para referirnos a autómatas finitos reconocedores (independientemente de si los mismos son deterministas o no deterministas)
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
expresiones regulares
Las expresiones regulares (ER) sobre un alfabeto Σ son cadenas sobre el alfabeto A = Σ ∪{(,),•, +,*, λ,∅} definidas recursivamente como sigue:
1. λ es una ER.2. ∅ es una ER.3. Todo símbolo a ∈ Σ es una ER.4. Si α y β son ER, entonces (α ), α•β,
α+β y α* también son ER.
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
lenguajes y expresiones regulares
Construimos la función L tal que si α es una ER entonces L(α) es el lenguaje representado por α:
1. L(λ) = {λ }.2. L(∅) = ∅.3. Para cada símbolo a ∈ Σ, L(a) = {a}.4. Si α y β son ER, entonces
L(α•β) = L(α)•L(β), L(α+β) = L(α)∪L(β), L(α*) = L(α)* .
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
lenguajes y expresiones regulares
Algunos ejemplos de ER sobre el alfabeto Σ={a,b}:
λ, ∅, a+ λ, a*(a+b)*b, b•a*Observaciones:1. El símbolo “•” (concatenación) podrá ser
obviado cuando ello no provoque ambigüedad. Por ejemplo la ER b•a* se escribirá como ba*.
2. Notar que el mismo lenguaje regular puede ser notado mediante diferentes expresiones regulares. Por ejemplo L((0+1)*) =L(((0+1*)*+(01)*)*)
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
equivalencia entre ER y AF
Teorema de Kleene (detalles en Hopcroft et al., sección 3.2):
Un lenguaje L puede ser expresado por una ER si y sólo si es reconocido por un AF.
PruebaParte 1: Dada una ER, construimos un AF.Parte 2: Dado un AF, construimos una ER.
Stephen Kleene1909-1994
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 1: ER → AF
1. λ.
2. ∅.
3. a ∈ Σ.
λ
a
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 1: ER → AF
4.1. α+β.
R
S
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 1: ER → AF
4.1. α+β.
R
S
λ
λ
λ
λ
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 1: ER → AF
4.2. α•β.
R S
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 1: ER → AF
4.2. α•β.
R Sλ
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 1: ER → AF
4.3. α*.
R
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 1: ER → AF
4.3. α*
Rλ
λ
λ
λ
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 2: AF → ER
Ejemplo AF → ER (informal)Escribir la expresión regular para los
siguientes AF
S0 S10,1
S20,1
0,11)
S0 S11
S31
0,12) 0
S20 0,1
0+1
0*10
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 2: AF → ER
LemaSi ω, β y γ son ER sobre un alfabeto Σ, γ≠ λ, entonces la ecuación ω= β + ωγtiene una única solución y está dada por ω= βγ*
S
γ
β
ωS= β + ωSγ ωS= βγ*
asociar cada estado con una ER
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 2: AF → ER
AlgoritmoEntrada: un AF M= (S, Σ, δ, s0 , F)Salida: una ER que denota el LR
reconocido por M.
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 2: AF → ER
Paso 1:Plantear una ecuación por cada
estado, como unión de n términos ωsi= ωsj1 • a1 + ωsj2 • a2 ....
Para δ(sj,a)=si, uno de los términos de la ecuación ωsi será ωsj•a.
En la ecuación para el estado inicial se agrega el término λ.
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 2: AF → ER
Paso 2:despejar ecuaciones según lema ω=β+ωγ entonces ω = βγ *
Paso 3:La ER es la unión de las soluciones
para todos los estados aceptadores del AF.
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 2: AF → ER
EjemploM= (S, Σ, δ, s0 , F) S = {s0, s1, s2}, Σ = {a,b}, F ={s1}
s0s2s2
s2s1s1
s1s0s0
baδ
S0 S1
S2
a a
a
bb
b
ωS0= ωS0a+ ωS2b + λωS1= ωS1a+ ωS0bωS2= ωS2a+ ωS1b
Paso 1: Planteamos ecuaciones
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 2: AF → ER
ωS0= ωS0a+ ωS2b + λ
Paso 2: ω=β+ωγ entonces ω = βγ *
ωS1= ωS1a+ ωS0b
ωS2= ωS2a+ ωS1b
ωS0= (ωS2b + λ)a*
ωS1= (ωS0b)a*
ωS2= (ωS1b)a*
γ=a y β=ωS2b + λ
γ=a y β=ωS0b
γ=a y β=ωS1b ωS1=(ωS0b)a*ωS1=((ωS2b + λ)a*b)a*ωS1=((ωS1b)a*b + λ)a*b)a*=ωS1ba*ba*ba*+a*ba*ωS1=a*ba*(ba*ba*ba*)*
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
Parte 2: AF → ER
Paso 3: La ER es la unión de las soluciones para todos los estados aceptadores del AF.
L(M) =a*ba*(ba*ba*ba*)*
S0 S1
S2
a a
a
bb
bωS1=a*ba*(ba*ba*ba*)*
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
propiedades de los lenguajes regulares
Lema: La clase de los lenguajes aceptados por AF, es decir la clase de los lenguajes regulares, es cerrada bajo:
unión, concatenación, estrella de Kleene, complemento e intersección.
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
gramáticas regulares o de tipo 3 (repaso)
Gramática Regular (tipo 3)Para cada producción α → β
(excepto S → λ): α ∈ VN y β es de la forma t o tW, donde t ∈ VT y W ∈ VN
EjemploS → aAA → aBB → a | aS
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
equivalencia entre gramáticas regulares y AF
Si G una gramática regular podemos obtener un autómata M tal que L(M) = L(G), y viceversa, dado el autómata M podemos construir la gramática G.
Mostramos un método simple y ejemplos:
Parte 1: Dada una gramática G mostraremos como construir un autómata M tal que L(G) = L(M).
Parte 2: Dado un autómata M mostraremos como construir una gramática G tal que L(M) = L(G)
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
gramática regular → AF
Parte 1: Dada G=(VN, VT,S,P) construimos M = (K, VT, δ, S, F) donde K=VN ∪ {A} con A nuevo (no perteneciente a VN)
Si P tiene la producción S →λ entonces F ={A,S} si no F = {A}.
Al definir δ debemos considerar los siguientes casossi B → a ∈ P entonces:
δ(B,a) ⊇ {A},a ∈ VT; B ∈ VN
si B → aC ∈ P entonces:δ(B,a) ⊇ {C},
a ∈ VT; B,C ∈ VN
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
gramática regular → AF
EjemploG=(VN, VT,S,P)VN ={S,B}VT={a,b}S → a | bBB → bB | b
S A
B
b
a
b b
M = (K, VT, δ, S, F)K ={S,A,B}F = {A} δ(S,a)={A}
.δ(S,b)={B}δ(B,b)={A,B}
autómatas finitos y
lenguajes regulares
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
AF → gramática regular
Parte 2: Dado M = (S, Σ, δ, s0, F) un AF determinista construimos G=(S, Σ, s0,P) donde P está formado por
s0 → λ, si s0 ∈ FB → aC, si δ(B,a) = C B → a, si δ(B,a) = C y C ∈ F
top related