2
$\begingroup$

Here is the grammar given on the wikipedia:

$$ S \rightarrow T \;|\; U \\ T \rightarrow VaT \;|\; VaV \;|\; TaV \\ U \rightarrow VbU \;|\; VbV \;|\; UbV \\ V \rightarrow aVbV \;|\; bVaV \;|\; \epsilon $$

I can understand how $V$ generates strings with equal number of a's and b's. I want to prove that $T$ generates strings with more a's than b's. The case for U can be proven symmetrically.

Here is my attempt and doubt.

$P(0)$: Suppose $s$ is a string with one extra a. Let $s_1$ be the longest balanced prefix of s. Then $s=s_1 t$ where t necessarily starts with $'a'$. For otherwise t will have a non-empty balanced prefix and $s_1$ won't be the longest prefix. Hence $s = s_1 a s_2$ where $s_1$ and $s_2$ are balanced and derivable from $V$. hence s can be derived as $S \rightarrow VaV=>^* s_1as_2$.

$P(n)$ : Suppose $T =>^* w$, where w has $n$ extra a's than b's. Let s be a string with $n+1$. Let $s_1$ and $t$ be as above. Then $t = aw$. By construction, $w$ has $n$ extra a's and is derivable from T. Therefore $T \rightarrow VaT =>^* s_1aw$.

My doubt is what is the need for the rule $T \rightarrow TaV$

$\endgroup$
4
  • $\begingroup$ Perhaps it’s not needed… $\endgroup$ Oct 16 at 12:01
  • $\begingroup$ @YuvalFilmus That's my thought as well. Can you confirm? $\endgroup$
    – somitra
    Oct 16 at 12:02
  • $\begingroup$ If you can generate all words in the language without using this rule, then it is not needed. $\endgroup$ Oct 16 at 12:26
  • $\begingroup$ Ok, I'll take that my proof is correct and the rule is not needed. Thanks $\endgroup$
    – somitra
    Oct 16 at 12:37
2
$\begingroup$

You said:

Here is the grammar given on the wikipedia:
[...]
$T \rightarrow VaT \;|\; VaV \;|\; TaV$
[...]
My doubt is what is the need for the rule $T \rightarrow TaV$

Wikipedia said:

Omitting the third alternative in the rules for T and U doesn't restrict the grammar's language.

$\endgroup$
1
  • $\begingroup$ I totally missed it $\endgroup$
    – somitra
    Oct 17 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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