0 votes 0 votes Give context-free grammars that generate the following languages$.$ In all parts, the alphabet $\sum$ is $\{0,1\}.$ $\text{{w| w contains at least three 1’s}}$ $\text{{w| w starts and ends with the same symbol}}$ $\text{{w| the length of w is odd}}$ $\text{{w| the length of w is odd and its middle symbol is a 0}}$ $\text{{$w|w=w^{R},$that is, w is a palindrome}}$ $\text{The empty set}.$ Theory of Computation michael-sipser theory-of-computation context-free-language context-free-grammar descriptive + – admin asked May 1, 2019 retagged May 1, 2019 by Lakshman Bhaiya admin 3.1k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes a. S->A1A1A1A A->0A | 1A | ε b. S->0A0 | 1A1 | 0 | 1 | ε A->0A | 1A | ε c. S->0S0 | 1S1 | 0S1 | 1S0 | 0 | 1 d. S->0S0 | 1S1 | 0S1 | 1S0 | 0 e. S->0S0 | 1S1 | 0 | 1 | ε aditi19 answered Aug 14, 2019 edited Aug 14, 2019 by aditi19 aditi19 comment Share Follow See all 0 reply Please log in or register to add a comment.