# Proving sets of regular expressions and context free grammars are decidable [duplicate]

Consider below languages:

1. $$L_1=\{|M$$ is a regular expression which generates at least one string containing an odd number of 1's$$\}$$
2. $$L_2=\{|G$$ is context free grammar which generates at least one string of all 1's$$\}$$

Its given that both above languages are decidable, but no proof is given. I tried guessing. $$L_1$$ is decidable, its a set of regular expressions containing

• odd number of $$1$$'s, or
• even number of $$1$$'s and $$1^+$$ or
• $$1^*$$

So we just have to parse regular expression for these characteristics. Is this right way to prove $$L_1$$ is decidable?

However, can we have some algorithm to check whether given input CFG accepts at least one string of all 1's? I am not able to come up with and hence not able prove how $$L_2$$ is decidable.

• Please ask only one question per post. – D.W. Dec 31 '19 at 20:08
• The problem did not talk about intersection of regular and context free languages, but whether they accept certain kind of words independently. – anir Jan 1 at 3:56
• The first listed dup (cs.stackexchange.com/questions/80713/…) seems to address exactly that, and also explains why intersection is relevant. – D.W. Jan 1 at 10:59