Cheap and Secure Web Hosting Provider : See Now

# [Answers] How to prove a L=L(G) without knowing the L?

, ,
Problem Detail:

How does one prove L(G)=L if the language is not given and only the grammar G is given? If there is no pattern to be seen in the grammar that would create the strings w of a language L, how would you go about doing this?

#### Answered By : Rick Decker

In cases like this, where you have a grammar and want to guess what the language is, a good way is to approach the problem systematically, by trying to derive some short strings. For example, if you had a grammar $G$ like this, \begin{align} S &\rightarrow SA \tag{1}\\ S &\rightarrow \epsilon \tag{2}\\ A &\rightarrow aS \tag{3}\\ A &\rightarrow bA \tag{4}\\ A &\rightarrow \epsilon \tag{5} \end{align} then here are a few derivations, where the relevant production is labeled: \begin{align} \epsilon&: S \stackrel{2}{\Longrightarrow}\epsilon\\ a&: S \stackrel{1}{\Longrightarrow} SA\stackrel{2}{\Longrightarrow}A\stackrel{3}{\Longrightarrow}aS\stackrel{1}{\Longrightarrow}a\\ b&: S \stackrel{1}{\Longrightarrow} SA\stackrel{2}{\Longrightarrow}A\stackrel{3}{\Longrightarrow}bA\stackrel{4}{\Longrightarrow}b\\ aa&: S \stackrel{1}{\Longrightarrow} SA\stackrel{1}{\Longrightarrow}SAA\stackrel{2}{\Longrightarrow}AA\stackrel{3}{\Longrightarrow}aSA\stackrel{1}{\Longrightarrow}aA\stackrel{3}{\Longrightarrow}aaS\stackrel{2}{\Longrightarrow}aa\\ \end{align} If you try this for, say $ab,ba,bb$, you'll find that they're all in $L$ which prompts a guess that this grammar generates all strings over the alphabet $\{a,b\}$. This isn't too hard to show, by induction on the length of a string in the language.

The proof goes like this:

Base. Show that the length-0 string, $\epsilon\in L(G)$. (We've done this already.)

Induction. Let $w$ be any string of length $n>0$. Our inductive hypothesis is that any shorter string, $z$ is in $L(G)$, i.e., there is a derivation $S\stackrel{*}{\Longrightarrow}z$. Now either $w=za$ or $w=zb$. We'll do one case and leave the rest to you: $$S\stackrel{1}{\Longrightarrow}SA\stackrel{3}{\Longrightarrow}SaS\stackrel{2}{\Longrightarrow}Sa\stackrel{*}{\Longrightarrow}za = w$$ so $w\in L(G)$, as required.