1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ It is completely meaningless to prove $L(G) = L$ if you only have $G$. We already know that $L(G) = L$ for some language $L$, namely the language defined by $L = L(G)$. What you are really asking is, given a grammar, how to describe the language it generates in a simpler way. This is a very general question and I'm not sure there is a simple answer. $\endgroup$ – Yuval Filmus Nov 30 '15 at 15:49
  • $\begingroup$ @YuvalFilmus I was asked on a test to find a prove some language was generated by a grammar G. I realized that the grammar G created a language (a+b)* and I need to prove this is true. $\endgroup$ – chamburger Nov 30 '15 at 16:14
  • $\begingroup$ Of course @YuvalFilmus is right. There is no simple answer to this. (In fact equality to $(a+b)^*$ is undecidable for context-free grammars, so how can we expect to determine the language for a grammar.) Yet I think it is a reasonable question that we should not close too soon. $\endgroup$ – Hendrik Jan Nov 30 '15 at 19:51
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @chamburger. Glad to be of help. By the way, welcome to the site. If you plan on asking another question, you might want to read this. $\endgroup$ – Rick Decker Nov 30 '15 at 16:52

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