2
$\begingroup$

I have to prove that the language $L=\{a^ib^j:2i=3j+1\}$ and the CFG G with the following rewrite rules:

$S\rightarrow a^2Tb$

$T\rightarrow a^3Tb^2 |\epsilon$

are equivalent to each other.

I'm going to prove this by saying $L(G)\subseteq L$ and $L \subseteq L(G)$. I was able to prove the first one. I should be able to prove the second one with induction on the length on a word $w$. But how can I do that? The induction basis should start at length 3, because the smallest word $w \in L$ is $aab$. But the second word has a length of 8. This means the stepsize in the induction proof is 5. I've never done an inductive proof with a stepsize different from 1. How can I do something like this as it's not possible to state in the induction step that "We assume that the theorem holds for $|w|=n$, now we are going to proof that it holds for $|w|=n+5$"?

UPDATE: I think I found a solution to my own question:

Inductionbasis: Suppose $|w|=3$. Then $w$ must be $aab$ because that's the only word of length 3 that satisfies the requirements for the language L. But $aab$ is also an element of $L(G)$. The basis is OK.

Induction hypothesis: Assume that the theorem holds for all words $w`$ with length $|w`|=3+5n$. We are now going to proof that the theorem also holds for all words $w$ with length $|w|=3+5(n+1)$.

$w$ must be of the form $\alpha a^3b^2 \beta$ to be an element of $L$. Now consider the word $z=\alpha \beta$ with length $|z|=3+5n$. Then, by induction, we know that $z \in L \implies z \in L(G)$. Because $z \in L(G)$ it must hold that $z$ is of the form $a^nb^m$ with $2n=3m+1$. If we add the 3 $a$'s and 2 $b$'s from $w$ to this equation, we find that $2(n+3)=3(m+2)+1$. The following applies to this equation:

$2(n+3)=3(m+2)+1$

$\iff 2n+6=3m+6+1$

$\iff 2n+6=3m+1+6$

$\iff 2n+6=2n+6$

Thus, $w$ also satisfies $L(G)$. QED

Is this proof correct?

$\endgroup$
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Mar 26 '17 at 23:11
  • $\begingroup$ cs.stackexchange.com/q/11315/755 $\endgroup$ – D.W. Apr 17 '17 at 6:39
1
$\begingroup$

Since this is a very simple "linear" grammar, its language can be determined by looking at the possible derivations.

Clearly a successful derivation has to start with $S\to a^2Tb$, then repeats $k$ times the production $T\to a^3Tb^2$ and closes with $T\to \epsilon$. That will give strings of the form $a^{2+3k}b^{1+2k}$ with $k\ge 0$. (1)

Then we need to establish that these are exactly the strings of the form $a^ib^j$ with $2i=3j+1$. (2)

One direction is easy, strings of the form (1) satisfy (2) -- you solved that yourself -- by observing that $2(2+3k) = 3(1+2k)+1$.

Your proof for the other direction sounds good, but it is not clear to me how one argues that the induction has step size $5$ (other than by trial and error).

The following would work. Start with (2) for natural numbers $i,j$.

This implies $3j+1$ is even (and non-negative).

Or, $3j$ is odd, so $j$ is odd, which means it is of the form $j=2k+1$ for $k\ge 0$.

Then $2i=6k+4$, or $i=3k+2$, and we are done.

This argument seems rather ad hoc. Note the similarity between this exercise and linear algebra. There are two different representations for a line in 2D: using vectors or equations. Here these are:

  • $\{ (2,1)+ k\cdot(3,2) \mid k\in \mathbb R \}$

  • $\{ (x,y) \mid 2x-3y=1 \}$

Unfortunately, I do not think linear algebra tricks directly work, as we here must restrict ourselves to integers and not the real numbers.

$\endgroup$

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.