Gramática libre de contexto para la lengua

Question

Tuve que hacer una gramática libre de contexto para el siguiente idioma: $$ \{a^m b^n \mid 1 \le m \le n \le 2m\} $$

Lo que he pensado es: \begin {align*} S & \to aXbb \\ X & \to a|aab|abb|ab|E \end {align*}

¿Es esta la forma correcta de escribir una CFG?

Answer 1

Es interesante ver tantas ideas diferentes. Mi propia sugerencia es que podemos producir palabras "creando" a s y b s de forma iterativa, y en cada paso podemos hacer una de estas dos cosas: crear una a y una b o crear uno a y dos b s.

(ten en cuenta que cada respuesta hasta ahora conduce a una presentación diferente de la gramática: no puedes combinar las pistas directamente, y probablemente sólo deberías pensar en una a la vez)

Answer 2

No es correcto. Considere la palabra $a^4b^5$ . Esta palabra pertenece a la lengua porque $m=4$ , $n=5$ y $1 \le 4 \le 5 \le 2 \times 4$ . Sin embargo, su gramática no puede producirlo, ya que puede producir tres " $a$ " como máximo.

Aquí hay una pista: Haga $S$ producir uno $a$ , uno $b$ y una $B$ recursivamente. Hacer $B$ producir uno $b$ como máximo. Esto garantiza que $1 \le m \le n$ y $n \le 2m$ .

Answer 3

Una pista: $$a^m b^n = a^{2m-n}a^{n-m}(bb)^{n-m}b^{2m-n}$$

Answer 4

CFG debe ser $$S\rightarrow aSb|aSbb|ab|abb$$ donde $S$ es el símbolo de inicio.
Así, por ejemplo, si tiene que producir la palabra $a^mb^n$ entonces como sabemos $m\leq n\leq 2m$ entonces se utilizará $2n-m$ veces esta producción ( $S \rightarrow aSb$ ) y $m-n$ veces esta producción ( $S \rightarrow aSbb$ ). por lo que obtendrá $(2n-m)+(m-n) \times a$ y $(2n-m)+2(m-n)\times b$ que se desea.

De nuevo si $m\leq n\leq km$ entonces CFG sería $$S\rightarrow aSb|aSbb|.....|aS\underbrace{bb....b}_{\text{k times}}|ab|abb|......|a\underbrace{bb....b}_{\text{k times}}$$ y aquí también la lógica es la misma.