1 votes 1 votes Which of the following is not context free? $I) L_{1}=\left \{ a^{i}b^{j}c^{k} |i,j,k\geq 0,i<j<k \right \}$ $I) L_{2}=\left \{ a^{i}b^{j}c^{k} |i,j,k\geq 0, j=max\left ( i,k \right )\right \}$ Theory of Computation context-free-language theory-of-computation + – srestha asked Nov 28, 2017 srestha 441 views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Manu Thakur commented Nov 28, 2017 reply Follow Share L1 is definitely not CFL as there are two comparisons with AND condition. L2 seems to be CFL but i need to check further. 1 votes 1 votes srestha commented Nov 28, 2017 reply Follow Share yes L2 need prefix property I think 0 votes 0 votes srestha commented Nov 28, 2017 reply Follow Share but think L1 like this a push on stack, then b pop and after finishing a ,push remaining b in stack, now pop b by c and then push c atlast pop all c Why cannot we do it in one stack? 0 votes 0 votes Manu Thakur commented Nov 28, 2017 reply Follow Share where is the comparison? aabbbbccc how will you reject this? 0 votes 0 votes srestha commented Nov 28, 2017 reply Follow Share See we know $a^{x}b^{x+y}c^{y}$ is CFL with one stack operation but is$a^{x}b^{x+y}c^{y+z}$ is Not a CFL? Can it not be done in one stack? Do we reject it? 0 votes 0 votes prateekdwv commented Nov 28, 2017 reply Follow Share We push all a's into the stack then pop them for each b we encounter in the input string. With this, we are done with $a^xb^x$. However, now when we compare the number of b's with the number of c's we can only compare $b^yc^{y+z}$. But in the input string entire $(x+y)$ must be less than $(y+z)$. It could be the case that $y < (y+z)$ but $(x+y)$ may not necessarly be less than $(y+z)$ 0 votes 0 votes just_bhavana commented Nov 29, 2017 reply Follow Share For $L_{2}$ we can just compare $i$ and $k$ If $i> k$ then $j=i$ else $j=k$ I think we'll require a non deterministic PDA for $L_{2}$ 1 votes 1 votes vamp_vaibhav commented Nov 29, 2017 reply Follow Share #Bhawna how will you check i>k if j counts in between.. I mean we can ignore counting of b but that would be again a problem to check whether j=i or not.. 0 votes 0 votes jatin saini commented Nov 29, 2017 reply Follow Share but there are two comparisons 1. i and k 2.j and k or j and i 0 votes 0 votes just_bhavana commented Nov 29, 2017 reply Follow Share @vaibhav yes you are correct. It will be difficult by that method to reject the strings not in the grammar as once we lose track of #$a's$ and if we encounter #$a's$ $\neq$ #$b's$ then we cannot backtrack to compare #$a's$ and #$c's$ 1 votes 1 votes Please log in or register to add a comment.