0 votes 0 votes Give context-free grammars generating the following languages. The set of strings over the alphabet $\{a,b\}$ with more $a's$ than $b's$ The complement of the language $\{a^{n}b^{n}\mid n\geq 0\}$ $\{w\#x\mid w^{R}$ $\text{is a substring of $x$ for }$ $w,x \in\{0,1\}^{*}\}$ $\{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}\}$ Theory of Computation michael-sipser theory-of-computation context-free-language context-free-grammar + – admin asked May 1, 2019 retagged May 1, 2019 by Lakshman Bhaiya admin 816 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply aditi19 commented Aug 14, 2019 reply Follow Share question 3 is a regular language I think? RE=(a+b)*#(a+b)* 0 votes 0 votes Arjun commented Aug 14, 2019 reply Follow Share How come? 0 votes 0 votes aditi19 commented Aug 14, 2019 reply Follow Share not sure... just guessed... I could be wrong 0 votes 0 votes Arjun commented Aug 14, 2019 reply Follow Share You should never guess in these topics :) 0 votes 0 votes Please log in or register to add a comment.
0 votes 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 | ε aditi19 answered Aug 14, 2019 edited Aug 14, 2019 by aditi19 aditi19 comment Share Follow See all 4 Comments See all 4 4 Comments reply Arjun commented Aug 14, 2019 reply Follow Share Can it generate $aab?$ 0 votes 0 votes aditi19 commented Aug 14, 2019 reply Follow Share @Arjun sir I've changed it pls check is it correct now? 0 votes 0 votes Arjun commented Aug 14, 2019 reply Follow Share For b part, you havent given bounds for $m,n$. Also $bab$ won't be generated rt? 0 votes 0 votes aditi19 commented Aug 14, 2019 reply Follow Share thanks for pointing out that @Arjun sir corrected :P 0 votes 0 votes Please log in or register to add a comment.