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?


closed as too broad by Yuval Filmus, Evil, Renato Sanhueza, cody, David Richerby Nov 30 '15 at 20:55

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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

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.

  • $\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.