Find a CFG for L = { a^nb^m : n != m }

Question

This question is upcoming for my midterm and I can't figure it out. My professor broke it down in two statements (n>m) and(m>n) and left us at that.

Find a context free grammar for $L = \{ a^n b^m : n \neq m \}$

Answer 1

You have two cases like your professor stated: $n > m$ and $n < m$. Let $x \to c_1$ and $x \to c_2$ be two rules that initiate the two cases, i.e. $x$ is the start variable. Then for example, for $n > m$ this is handled by $c_1$ and the context free grammar rules to generate it are $c_1 \to a$, $c_1 \to a c_1 b$, and $c_1 \to a c_1$. Similarly for $c_2$ to handle the case $n < m$.

Answer 2

Hint:

• $\{a^nb^m \mid n < m\} = \{a^nb^n \mid n \in \mathbb{N}\} \circ \{b^k \mid k \geq 1\}$
• $\{a^nb^m \mid n > m\} = \{a^k \mid k \geq 1\} \circ \{a^nb^n \mid n \in \mathbb{N}\}$
• Assuming that $X$ generates $\{a^nb^n\}$, start with $S \to XB \mid AX$.

I hope this helps $\ddot\smile$

Answer 3

yes,the idea to form grammars for this falls in two divisions 1)nm so lets define the grammar for each individually and combine.
S -> X | Y
X -> aXb | Xb | b
Y -> aYb | aY |a

Answer 4

In this problem, strings start with a number of a's followed by the number of b's. there may be two cases

1. number of a's are greater than the number of b's , so we can assume that i) number of a's are equal as number of b's and after that we have to generate at least one extra a in the string so productions are S--> aSb | A A--> aA|a
2. number of b's are greater than the number of a's , so we can assume i) number of a's are equal as number of b's and after that we have to generate at least one extra b in the string so productions are S--> aSb | B B-->bB|b Hence Grammar productions are S-->aSb|A|B A--> aA|a B-->bB|b

Answer 5

As per the given problem we have two cases i.e.

1. either the number of a can be greater than b (when n > m)
2. or the number of b can be greater than a (when m > n).

The minimum string that need to be generated is either a or b.

Then this production rule must satisfy all the conditions:

S -> Sa | Sb | E | a | b