3
$\begingroup$

So at the beginning I was aiming at $L_{a\neq b} = \{w\in \{a,b\}^* : \#_a(w) \neq \#_b(w) \}$. But figured out that is would be better to first deal with: $L_{a>b} = \{w\in \{a,b\}^* : \#_a(w) > \#_b(w) \}$, due to the fact that $L_{a>b} \cup L_{b>a} = L_{a\neq b}$.

My attempts so far for $L_{a>b}$ - I proved that this language is pump-able: Choosing $N=2$ For $z\in L$ contains only $a$s the pump it pretty basic, on the other hand words contain $b$s: $\#_b(z) > 0 \Rightarrow \#_a(z) > \#_b(z) >0 $ so $z$ must include the couple $ab$ or $ba$ as a sub string, so $ z= \gamma ab\delta \Rightarrow \gamma|a|\varepsilon|b|\delta$ is a valid splitting, and $\gamma a^ib^i\delta\in L$ because the relation between $a$'s and $b$'s appearances is preserved.

So I was hoping this language might be context free and tried to form a Grammar which generates the language, However I didn't succeed in it, due to the fact that a general word of the form: $a^{i_1}b^{j_1}a^{i_2}b^{j_2}...a^{i_n}b^{j_n}$ when $i_k,j_k \in \mathbb{N}\cup\{0\}$ satisfies $\sum i_k > \sum j_k$ and I am having hard time dealing with cases in which $i_l <j_l$ (for example $aaaababb$ when the second pair is $abb$).

I don't know whether I may proceed from my best attempt, yet, in case $ z = a^{i_1}b^{j_1}a^{i_2}b^{j_2}...a^{i_n}b^{j_n}$ satisfies $i_k > j_k \forall k\in [n]$ The grammar $A\rightarrow a | AA|AAB|BAA , B\rightarrow b$ with A as the initial term, should work (I didn't formally prove it so I might be wrong).

I also tried to work with closure properties but couldn't even find an idea to start with...

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Here is a hint. Given a word in $L_{a\gt b}$, if you remove $ab$ or $ba$ from it repeatedly until you cannot any more, what kind of word will you end up with?

Here is an almost complete answer.

The language $L_{a\gt b}$ is similar to the language where the number of "a"s is equal to the number of "b"s, except there can be arbitrary number of extra "a"s at any position and there must be at least one extra "a" somewhere.

Here is its context-free grammar:
$\quad S \to TaT$
$\quad T \to TT|bTa|aTb|aT|\epsilon$

As a part of a proof that the above grammar generates $L_{a\gt b}$, let us show that $T$ stands for a word that has no less "a"s than "b"s. $T$ can only generate such kind of word, since whenever a "b" is included, an "a" is included. Now suppose $Z$ is such a word that is not empty. There are two cases.

If $Z$ starts with a "b", let us walk through the symbols in $Z$ from its beginning, counting how many "a"s and how many "b"s along the way. So initially we have zero "a" and one "b". At some point of this walk, we will count an equal number of "a"s and "b"s since $Z$ has no less "a"s than "b"s. That means $Z=bXaY$ for some words $X$ and $Y$, where $bXa$ has the same number of "a"s and "b"s and where $Y$, the remaining part, must have no less "a"s than "b"s. Note that both $X$ and $Y$ are shorter than $Z$.

The other case is when $Z$ starts with an "a", that is, $Z=aW$ for some word $W$. If $W$ has no less than "a"s than "b"s, we are in good condition since $W$ is shorter than $Z$. Otherwise, $W$ has (exactly one) less "a"s than "b"s. There are two subcases. If $W$ ends with a "b", then $Z=aUb$, where $U$ has no less "a"s than "b"s and $U$ is shorter than $Z$. Otherwise, $W$ ends with an "a". Now let us walking through symbols of $W$ from its end, counting the number of "a"s and the number of "b"s along the way. At some point of our walk, we will count an equal number of "a"s and "b"s. That means $W=UV$ for some word $V$ that has the same number of "a"s and "b"s. So $Z=aUV$, where $aU$ must have no less "a"s than "b"s. Note that both $U$ and $V$ are shorter than $Z$.

The preceding two paragraphs shows that $Z$ must comes from two or one shorter word that also has no less "a"s than "b"s by the production rule of $T$. Since $T$ can be replaced by the empty word $\epsilon$, we see that $T$ can generate all words that has no less "a"s than "b"s.

Exercise
Is the language $L_{a\gt b\gt c} = \{w\in \{a,b,c\}^* \vert \#_a(w) > \#_b(w) > \#_c(w)\}$ context free?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry for postponing my positive feedback, I hadn't succeeded to find a general method to generate each $w\in L_{a>b}$ using the grammar you suggested. $\endgroup$
    – user5721565
    Commented Sep 17, 2018 at 13:29
  • 1
    $\begingroup$ Have you shown that the second rule in my grammar generates the language that contains exactly all words whose number of "a"s is greater than or equal to its number of "b"s? $\endgroup$
    – John L.
    Commented Sep 17, 2018 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.