Find word made of same letters in CFG

Question

I had this one on exam and didn't know how to do it.

We have $\Sigma = \{a,b\}$. Write and algorithm in pseudo-code, that will decide whether our CFG will have a word $x^n$ for $x\in\Sigma$ and $|x|>0$

Can someone help me out with this?

Answer 1

You mean $n>0$? (Because if $x\in \Sigma$ then $|x|=1$ so $|x|>0$ does not help).

The answer depends a little on what tricks you are allowd to use here. The most high-level answer is to note that CFL are closed under intersection with regular languages, so we can construct a grammar $G'$ for which $L(G') = L(G) \cap (\{a\}^+ \cup \{b^+\}) $. Then decide emptiness, i.e., decide whether $L(G') = \emptyset$.

If you cannot use the "abstract" construction, we can give an explicit solution for it. There are only two options, either we must derive a word with only $a$'s or one with only $b$'s. Given your original grammar $G$ make a new grammar $G_a$ where you delete all productions that have terminal symbols other than $a$, so you delete all productions that involve $b$. Then $L(G_a) = L(G) \cap a^*$.

Then, we must assure that $G_a$ does not generate the empty word, because it is not wanted in the statement of the question. There are several ways to do that, but making your grammar into Chosmky Normal Form usually also looses the empty word. (And in fact, some books do not allow the empty word in grammars, which would solve that problem.)

Now, I hope you have had a method to decide emptiness of the language generated?