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?

Improve this question
$\endgroup$
2
  • $\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, 2018 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, 2018 at 17:37

1 Answer 1

Reset to default
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?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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