Prove that the following language is context-free by giving a context-free grammar that generates the language: $A = \{a \in \{0,1\}^* : \text{ no character in an even position is a 0 or no character in an odd position is a 1}\}$, where the first position is position 1. For instance, $01110, 01010$ are both in $A.$

If A were regular, I could convert a DFA for A into a CFG. I know I need to keep track of the parity of the positions of a character in a string. Basically, it should suffice to generate a CFG for the language $\{a\in \{0,1\}^* : \text{ no character in an even position is a 0}\}$, which consists of all strings where every character in an even position is a 1 and where the characters in all other positions can be 0 or 1. I think constructing this language should be symmetric to constructing the language that's the "other part" of $A$, namely $\{a\in \{0,1\}^* : \text{ no character in an odd position is a 1}\}$.

  • 3
    $\begingroup$ If you're trying to improve your skills, wouldn't it make more sense to solve these problems yourself? Even if you don't succeed right away, you're bound to learn something in the attempt. $\endgroup$
    – rici
    Jun 13, 2022 at 19:41

1 Answer 1


This language is regular and this is an NFA that describes it:


Please notice that the language has nothing to do with "counting" and it doesn't need any memory so you can simply realize it's regular, CFL uses the stack for memory purposes but here it's all about determining the place of a character.


Your Answer

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

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