2
$\begingroup$

I have an assignment, it's asked to write a context free grammar recognising the language $L=\{ w \mid w\text{ has an even number of }0\text{s and an odd number of }1\text{s}\}$, over the alphabet $\{0,1\}$.

My first guess was:

$$ \begin{align} S &\rightarrow A1A\\ A &\rightarrow A0A0A \mid A1A1A \mid \varepsilon \end{align} $$

But I realized it's wrong, since, for example, it doesn't accept the string $01011$ (I think my CFG forces pairs of $0$s).

Any suggestion?

$\endgroup$
  • $\begingroup$ From the four state automaton, You can use the Arden's theorem to find regular expression from which it is easy to find the regular grammar. $\endgroup$ – Deep Joshi Aug 31 '18 at 11:20
  • 1
    $\begingroup$ @DeepJoshi The regular expression is pretty horrible. I don't think that's the best way to go. (Unless I've underestimated the complexity of the method I suggest in my answer.) $\endgroup$ – David Richerby Aug 31 '18 at 17:37
2
$\begingroup$

This language is, in fact, regular – it is accepted by an automaton with just four states. I suggest that you first figure out what this automaton is and use what you learn to figure out a grammar. In particular, you don't need any context-free "tricks" or techniques.

If you need to, mouse-over the yellow area below to see a more detailed hint for the automaton.

Think about what data you need to know when you reach the end of the string, in order to decide if your input is in the language. What is the value of that data when you haven't read any input? How do you update that data as you read the input?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.