1,816 views

1 Answer

0 votes
0 votes

(a)     

  • Inductive Hypothesis: 

Sentential form $A_{n}$ of length $n$ has exactly $1$ non-terminal (i.e $S$), and has form $a^{i}Sb^{j} (0 \leq i,j)$.

 

  • Inductive step

From Production rules of grammar it's easy to see that after substituting any of first two productions, 

form of Sentential form $A_{n+1}$ remains $a^{i+1}Sb^{j} (0 \leq i,j)$ or  $a^{i}Sb^{j+1} (0 \leq i,j)$.

Upon applying production 3 or 4 form of string derived will have form $a^{i+1}b^{j} (0 \leq i,j)$ or $a^{i}b^{j+1} (0 \leq i,j)$  respectively.

 

  • Basis of induction: 

For  sentential form of length 1 our assumption that it has form $a^{i}Sb^{j} (0 \leq i,j)$ is true.

     

Now because every string derived from grammar have form $a^{i+1}b^{j} (0 \leq i,j)$ or $a^{i}b^{j+1} (0 \leq i,j)$, we can say that substring $ba$ will never occur in any string derived from this grammar.

                                    

(b)

         language generated by given grammar is set of all strings having arbitrary number of a's followed by arbitrary number of b's.

Related questions

0 votes
0 votes
1 answer
1
admin asked Apr 6, 2019
1,244 views
Consider the CFG $G$ defi ned by productions$:$$S\rightarrow aSbS|bSaS|\in$Prove that $L(G)$ is the set of all strings with an equal number of $a's$ and $b's.$
0 votes
0 votes
0 answers
4
admin asked Apr 11, 2019
307 views
Modify the $CYK$ algorithm to report the number of distinct parse trees for the given input, rather than just reporting membership in the language$.$