CFG para este idioma

Question

Tengo este lenguaje $L=\{a^nb^m|n\not = m; n,m \in \mathbb{N}\}$ Tengo que hacer CFG para este lenguaje pero no tengo ni idea.

Answer 1

Sugerencia . Si $n > m$ entonces $a^n b^m = a^{n-m} a^m b^m$ . Si $n < m$ entonces $a^n b^m = a^n b^n b^{m-n}$ . Por lo tanto, las cadenas en $L$ se obtienen a partir de las cadenas de la forma $a^n b^n$ añadiendo uno o varios $a$ al principio, o uno o más $b$ al final.

Answer 2

Dividido en dos casos: $m > n$ y $m < n$ . Supongamos que $L_1 = \{a^nb^m \mid n > m\}$ . Podemos escribir $L_1$ como \begin{align*} L_1 & \rightarrow a \\ L_1 & \rightarrow aL_1 \\ L_1 & \rightarrow aL_1b \end{align*} $L_2 = \{a^nb^m \mid n < m\}$ pueden ser tratados de forma similar: \begin{align*} L_2 & \rightarrow b \\ L_2 & \rightarrow L_2b \\ L_2 & \rightarrow aL_2b \end{align*} Entonces $L$ es la unión de $L_1$ y $L_2$ : \begin{align*} L & \rightarrow L_1 \\ L & \rightarrow L_2 \end{align*}