0
$\begingroup$

I figured out that the CFG that starts and ends with the same symbol in alphabet $\Sigma=\{0,1\}$ will be : S -> 0A0|1A1|0|1|

A -> 0A|1A|𝜖

How can i interpret the odd number of 1's also?

$\endgroup$
2
  • $\begingroup$ Let $B$ be the set of all strings with an even number of 1's, and $C$ the set of all strings with an odd number of 1's. Write productions for $B$ and $C$ (depending on each other). Then figure out how to modify the $S$ you already wrote. $\endgroup$
    – Joppy
    Nov 23 '20 at 22:39
  • $\begingroup$ Your language is regular. Construct a regular expression and convert it to a context-free grammar. $\endgroup$ Nov 23 '20 at 22:51

Your Answer

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

Browse other questions tagged or ask your own question.