La gramática regular de la lengua L = {a n b m | n + m es par} está dada por
(A) S → S 1 | S 2
S 1 → un S 1 | UN 1
UN 1 → segundo UN 1 | λ
S 2 → aaS 2 | UN 2
UN 2 → segundo UN 2 | λ
(B) S → S 1 | S 2
S 1 → un S 1 | aA 1
S 2 → aaS 2 | Un 2
Un 1→ segundo UN 1 | λ
UN 2 → segundo UN 2 | λ
(C) S → S 1 | S 2
S 1 → aaa S 1 | aA 1
S 2 → aaS 2 | UN 2
UN 1 → segundo UN 1 | λ
UN 2 → segundo UN 2 | λ
(D) S → S 1 | S 2
S 1 → aa S 1 | UN 1
S 2 → aaS 2 | A 2
A 1 → bb A1 | λ
A 2 → bb A 2 | λ
Respuesta: (D)
Explicación: Dado, lenguaje,
L = {a^n b^m | n + m is even}
Aquí m+n debe ser par para esto m, n debe ser par o m, n debe ser impar.
Ahora necesitamos generar una string como { $,ab, aa , bb,abbb, aaab,aabb,…….} para esta gramática debería ser,
S = S1 | S2 S1 = aa S1| A1
Aquí, dadas las reglas de producción, A1 deriva un número par de b, por lo que no tenemos ningún problema, S1 también deriva un número par de a.
S2 = aaS2| A2
En esta producción, A2 también deriva un número impar de b y A2 tendrá un número par de a y b.
A1 = bb A1| λ
Esta producción también deriva un número par de b.
A2 = bb A2| λ
Esto deriva un número impar de b, todos cumplen la condición dada del idioma dado.
Entonces, la opción (D) es correcta.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA