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
