# prove $A$ is context-free

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}\}$$.

• 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.
– rici
Jun 13, 2022 at 19:41