2 votes 2 votes L={ ai bj ck | i,j,k>=0, i<j<k} CFL OR NOT CFL ?? Theory of Computation context-free-language normal theory-of-computation + – focus _GATE asked Jan 10, 2017 retagged Oct 13, 2017 by Arjun focus _GATE 505 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply focus _GATE commented Jan 10, 2017 reply Follow Share it is CFL ryt ? 0 votes 0 votes Lokesh . commented Jan 10, 2017 reply Follow Share two comparison i<j and j<k ..not cfl 1 votes 1 votes focus _GATE commented Jan 10, 2017 reply Follow Share k got now thank u :) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes It's clearly a CSL. PDA cant do this as it contains only one stack. If we first compare a and b then we have no b to compare with c (as b is popping for a). So its not CFL. Rupendra Choudhary answered May 29, 2017 Rupendra Choudhary comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes It's a CSL because there are two comparisons and CFL can not handle such languages. To handle these languages LBA is strong enough because it can move left or right on an input tape, so we can move left to right n number of times. Sumit Singh Chauhan answered Aug 16, 2018 Sumit Singh Chauhan comment Share Follow See all 0 reply Please log in or register to add a comment.