prove that LG is the set of all non empty Let G V sigma R S

Let G = (V, sigma, R, S) be the context-free grammar, where V = {A, B, S}, sigma = {a, b}, S is the start variable, and R consists of the rules S rightarrow aB|bA A rightarrow a|aS|BAA B rightarrow b|bS|ABB Prove that ababba elementof L(G). Prove that L(G) is the set of all non-empty strings w over the alphabet {a, b} such that the number of as in w is equal to the number of bs in w. Let A and B be context-free languages over the same alphabet sigma. Prove that the union A union B of A and B is also context-free. Prove that the concatenation AB of A and B is also context-free. Prove that the star A* of A is also context-free. Define the following two languages A and B: A = {a^m b^n c^n: m greaterthanorequalto 0, n greaterthanorequalto 0}

Solution

The above question can be proved using induction method.

Claim: For all n, S -> (n steps) alpha. #_a(alpha) = #_b(alpha)

Base Case: n = 1. In one step, S -> aB | bA . With simplest replacement from A/B, S -> ab | ba. All these strings in base case has equal number of a\'s and b\'s.

Assumption: S -> (k steps) beta, #_a(beta) = #_b(beta) where beta could be of the form alpha S gamma

In the next k+1 step, S would expand either to aB | bA which we have seen already in base case that in the expansion number of a\'s would be equal to number of b\'s.

Hence using the principle of induction, we can prove that for all n, S -> (n steps) alpha. #_a(alpha) = #_b(alpha)