1 votes 1 votes Assume $\sum = \left \{ a,b \right \}$ $L = \left \{ w : n_{a}\left ( w \right ) = n_{b}\left ( w \right ) + 1 \right \}$ $L = \left \{ w : n_{a}\left ( w \right ) > n_{b}\left ( w \right ) \right \}$ $L = \left \{ w : n_{a}\left ( w \right ) = 2n_{b}\left ( w \right ) \right \}$ $L = \left \{ w \in \left \{ a,b \right \}^{*} : \left |n_{a}\left ( w \right ) - n_{b}\left ( w \right ) \right | = 1 \right \}$ Theory of Computation theory-of-computation peter-linz peter-linz-edition4 grammar + – Mk Utkarsh asked Feb 26, 2018 • edited Mar 4, 2019 by Naveen Kumar 3 Mk Utkarsh 1.2k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Jason commented Feb 26, 2018 reply Follow Share All are $DCFL.$ 0 votes 0 votes Mk Utkarsh commented Feb 26, 2018 reply Follow Share ok but grammars? atleast for (1) 0 votes 0 votes Please log in or register to add a comment.
Best answer 4 votes 4 votes 1) S -> aX / XS X -> XX / aXb / bXa / $\epsilon$ ( Thanks @Tarun kushwaha 1 ) 2) S-> aSb | bSa | SS |A A-> aA | a 3) S-> aaSb | bSaa |aSba|abSa|SS|ε (thanks @srestha) 4)S -> aX | bX | XS X -> aXb | bXa | XX |ε Tesla! answered Feb 27, 2018 • edited Nov 22, 2018 by Tesla! Tesla! comment Share Follow See all 13 Comments See all 13 13 Comments reply Show 10 previous comments Mk Utkarsh commented Feb 27, 2018 reply Follow Share not able to generate aba from 3rd one 0 votes 0 votes srestha commented Feb 27, 2018 reply Follow Share it will be S-> aaSb | bSaa |aSba|abSa|SS|ε 1 votes 1 votes Gurdeep Saini commented Nov 22, 2018 reply Follow Share @tesla typing mistake in the line 3) S-> aaSb | bSaa |SS|aSba|abSaε 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes Grammar for 1st.. S --> aX / XS X --> XX / aXb / bXa / λ Tarun kushwaha 1 answered Feb 27, 2018 Tarun kushwaha 1 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes are the following grammars correct ? 1. S-> aA / Aa A -> aAbA / bAaA / ϵ 2. S -> aSbS / bSaS / aS / a 3. S -> aaSbS / bSaaS / ϵ 4. S -> aSbS / bSaS / a /b Ananya Jaiswal 1 answered Feb 27, 2018 Ananya Jaiswal 1 comment Share Follow See all 3 Comments See all 3 3 Comments reply Mk Utkarsh commented Feb 27, 2018 reply Follow Share not able to generate aba from 3rd one 0 votes 0 votes Ananya Jaiswal 1 commented Feb 27, 2018 reply Follow Share yes i missed that. Thankyou. 0 votes 0 votes Mk Utkarsh commented Feb 27, 2018 reply Follow Share and not able to generate abbaaa from 2nd one 0 votes 0 votes Please log in or register to add a comment.