in

Encontrar el lenguaje creado por una gramática y determinar si puede ser creado por una gramática lineal derecha

Dada una gramática formal definida por
$$ S\rightarrow SaSbS | SbSaS | como| un | \varepsilon $$
necesito

Describa el lenguaje creado por la gramática y determine si este lenguaje puede ser creado por una gramática lineal derecha, si puede, defínalo, de lo contrario pruebe que no existe tal gramática.

La única manera que encontré para describir este lenguaje es $$L=\{w\en \Sigma^*|\#_a(w) >= \#_b(w)\}, \Sigma=\{a,b\}$$ aunque no se si esto es correcto.

Traté de encontrar si hay una gramática lineal derecha que crea $L$. Pero no creo que lo haya, ya que no hay manera de asegurar el número de $a$‘s en la palabra es mayor que el número de $b$‘s o igual a él, utilizando $$S\rightarrow\varepsilon | un| como | $$ reglas de derivación, pero no sé cómo demostrarlo.

EDITAR: Sé de una manera de probar esto. Si la gramática lineal derecha para $L$ existe entonces hay n autómata finito, $A$tal que $L(A) = L$por lo tanto $L$ es regular, así que para probar que no existe tal gramática, necesito probar que $L$ no es regular (y si lo es que hay una gramática lineal derecha)

0

¿Te ayudó la respuesta?

Subscribirse
Notificar por
guest
0 Comentarios
Inline Feedbacks
Ver todas las Respuestas

¿Quién es Lor San Tekka?

¿Cómo asumimos la dirección de $u_{\theta}$ y $u_{r}$ en sistemas de coordenadas polares?