View
219
Download
0
Category
Preview:
Citation preview
8/17/2019 Automatas y Lenguajes Formales (Gramáticas)
1/2
Tarea 5
Autómatas y Lenguajes Formales
Andrés López Martı́nez
Facultad de Ciencias, Universidad Nacional Autónoma de México
Marzo 10, 2016
1. Da una gramática que genere los siguientes lenguajes. Especifica sis 4 componentes.
(a) {w ∈ {a, b}∗ | w tiene un número par de a’s y un número impar de b’s}Soluci´ on: G = (N , T , P , S ) con:N = {A , B , C , D}
T = {a, b}P ={ S → A, A → aB, A → bC , B → aA, B → bD,C → aD, C → bA, C → ε, D → aC , D → bB
}
(b) {xyzyR ∈ {a, b}∗ | x, y, z ∈ {a, b}∗}Soluci´ on: G = (N , T , P , S ) con:N = {T, #, C }T = {a, b}P ={ S → ε, S → #T , T → aT a, T → bT b, T → C ,
# → a#, # → b#, # → ε, C → aC , C → bC ,
C → ε}
(c) {xyzyRx ∈ {a, b}∗ | x, y, z ∈ {a, b}∗}Soluci´ on: G = (N , T , P , S ) con:N = {T, #, C , P , Φ, Ψ}T = {a, b}P ={ S → ε, S → T #, T → aT a, T → bT b, T → C ,
Ca → C P a, Cb → C P b, P aa → aP a,P ab → bP a, P ba → aP b, P bb → bP b,P a# → #a, P b# → #b, C # → Φ
Φ → aΦa, Φ → bΦb, Φ → Ψ, Ψ → aΨ, Ψ → bΨΨ → ε}
(d) Identificadores en Java.Soluci´ on: G = (N , T , P , S ) con:N = {Φ, Ψ}T = {0, 1, ..., 9, a, b..., z,A,B,..., Z, , $}
1
8/17/2019 Automatas y Lenguajes Formales (Gramáticas)
2/2
P ={ S → Φ, Φ → aΨ|...|zΨ, Φ → AΨ|...|Z Ψ,Φ → Ψ, Φ → $Ψ, Ψ → aΨ|...|zΨ, Ψ → AΨ|...|Z Ψ,Ψ → 0Ψ|...|9Ψ, Ψ → Ψ, Ψ → $Ψ, Ψ → ε
}
2
Recommended