The Gateway to Computer Science Excellence
0 votes
32 views

Give context-free grammars that generate the following languages$.$ In all parts, the alphabet $\sum$ is $\{0,1\}.$

  1. $\text{{w| w contains at least three 1’s}}$
  2. $\text{{w| w starts and ends with the same symbol}}$
  3. $\text{{w| the length of w is odd}}$
  4. $\text{{w| the length of w is odd and its middle symbol is a 0}}$
  5. $\text{{$w|w=w^{R},$that is, w is a palindrome}}$
  6. $\text{The empty set}.$
in Theory of Computation by Veteran (59.3k points) | 32 views

1 Answer

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 | ε
by Loyal (5.2k points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,384 answers
198,541 comments
105,340 users