0
$\begingroup$

Consider below languages:

  1. $L_1=\{<M>|M$ is a regular expression which generates at least one string containing an odd number of 1's$\}$
  2. $L_2=\{<G>|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.

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

0

Reset to default