# Rough sketch for an Algorithm to show that a context free grammar G generates only words that are solely made up of b's

The title is a bit long but bare with my english skills. As the title says I have a the task to give a rough sketch for an algorhitm that checks whether a give grammar G, with the alphabet {a,b,c}, generates only words which are solely made up of b's. The hint given is to that we are allowed to use algorhitm's already shown in the lecture as parts of the sketch.

My idea was to use part of the algorhitm to convert a context free grammar into Chomsky normal form (no clue if the translation is correct). I just want to use the part's one and two. One is where all non-generating and all non-reachable Variables are removed from the Grammar. Two then seperates Variables and terminals by replacing occurences of a Variable x with a Variable $$W_x$$ with a rule of the form: $$W_x \to x$$ . In my head after that is done, if the grammar does not fullfill the condition, then I should be able to find a Variable X in the Grammar which has a rule of the form : $$X \to a$$ or $$X \to c$$.

In the end my question is just if this is a valid idea or if I should search for another idea to use?

For the definitions of a generating and a reachable Variable: A variable X of the grammar, with the starting Variable being S, is reachable if the is a derivation of the form: $$S \Rightarrow^* \alpha X \beta$$

A variable X of the grammar is generating if there is a derivation of the form: $$X \Rightarrow^* w$$ with $$w \in \Sigma^*$$

## 1 Answer

Your approach is fine. It suffices to remove all useless non-terminals, then check whether the result grammar contains any $$a$$ or $$c$$.

Alternatively: Since $$G$$ is context-free, so is $$L(G) \cap (\Sigma^* \setminus b^*)$$. It suffices to test whether the latter language is non-empty. Now there are standard algorithms for intersection with a regular language and testing emptiness of a context-free language.

• Thanks for the reply! The solution using intersection and testing for emtpiness also looks interesting. We definitly had a algorhitm to test for emptiness so might as well use that, thanks. Commented Jun 5 at 22:08