retagged by
350 views

1 Answer

Best answer
2 votes
2 votes
We can break this language into the union of several simpler languages: $L = \left \{ a^{i} b^{j}|i >j\right \}\cup \left \{ a^{i} b^{j}|i <j\right \}\cup \left \{ a\cup b \right \}^*b\left \{ a\cup b \right \}^* a\left \{ a\cup b \right \}^*$

That is, all strings of $a$ ’s followed by $b$ ’s in which the number of $a$ ’s and $b$ ’s differ, unioned with all strings, not of the form $a^{_{}i}b^{j}$

 
First, we can achieve the union of the CFGs for the three languages:

$S\rightarrow S_{1} | S_{2}|S_{3}$

 
Now the set of strings $\left \{ a^{i} b^{j}|i >j\right \}$ is generated by a simple CFG:

$S_{1}\rightarrow aS_{1}b | aS_{1}| a$

Similarly for $\left \{ a^{i} b^{j}|i <j\right \}$ :

$S_{2}\rightarrow aS_{2}b | S_{2}b| b$.

 
Finally $\left \{ a\cup b \right \}^*b\left \{ a\cup b \right \}^* a\left \{ a\cup b \right \}^*$ is easily generated as follows:

$S_{3}\rightarrow XbXaX$

$X\rightarrow aX|bX|\epsilon$
selected by

Related questions

0 votes
0 votes
1 answer
1
moe12leb asked Jan 21, 2023
276 views
S→ aS | bS | epsilonwhat is the language generated by this grammar ?
0 votes
0 votes
2 answers
2
moe12leb asked Jan 21, 2023
269 views
what is the langauge generated by this grammar ?S >aS | aSbS | ε what is the language
0 votes
0 votes
0 answers
3
moe12leb asked Nov 28, 2022
220 views
Find context-free grammars for the following languageL = { w : na(w) = 2nb(w); where w belongs {a, b}*}