The Gateway to Computer Science Excellence
0 votes
27 views

Give context-free grammars generating the following languages.

  1. The set of strings over the alphabet $\{a,b\}$ with more $a's$ than $b's$
  2. The complement of the language $\{a^{n}b^{n}\mid n\geq 0\}$
  3. $\{w\#x\mid w^{R}$ $\text{is a substring of $x$ for }$ $w,x \in\{0,1\}^{*}\}$
  4. $\{x_{1}\#x_{2}\#...\#x_{k}\mid k\geq 1,$ $\text{each}$  $ x_{i}\in\{a,b\}^{*},$ $\text{and for some i and }$ $ j,x_{i}=x_{j}^{R}\}$
in Theory of Computation by Veteran (55k points) | 27 views
0
question 3 is a regular language I think?

RE=(a+b)*#(a+b)*
0
How come?
0
not sure... just guessed... I could be wrong
0
You should never guess in these topics :)

1 Answer

0 votes
a.  S->AaA

     A->AA | aAB | bAa | a |  ε

     B->b

b.  $\overline{L}$={$a^nb^m | n>m>1$}  $\cup$  {$a^nb^m | m>n>1$} $\cup$ {(a+b)*b(a+b)*a(a+b)*}

     Grammar for $\overline{L}$:

     S->A | B | DbDaD

     A->aaAb | aaCb

     B->aBbb | aCbb

     C->aCb | ε

     D->aD | bD | a | b | ε
by Active (5.1k points)
edited by
0
Can it generate $aab?$
0

@Arjun sir

I've changed it

pls check is it correct now?

0
For b part, you havent given bounds for $m,n$. Also $bab$ won't be generated rt?
0

thanks for pointing out that @Arjun sir

corrected :P

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,645 questions
56,597 answers
195,837 comments
102,127 users