retagged by
505 views
2 votes
2 votes

L={ ai bj ck | i,j,k>=0, i<j<k}
CFL OR NOT CFL ?? 

retagged by

2 Answers

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.
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.

Related questions

0 votes
0 votes
2 answers
1
Anmol Verma asked Dec 2, 2016
690 views
Is L={$a^{n}b^{n}c^{m}$ : n>m} context free...???
0 votes
0 votes
0 answers
2
saptarshiDey asked Jan 22, 2019
525 views
L = {a^(p+q) b^(p+q) a^p , p,q>=0}Which one of the following is true about L?L is a regularL is CFL but not regularL is not a CFL
2 votes
2 votes
0 answers
3
gari asked Jan 12, 2018
247 views
the condition is 1) (i<=j) or (j<=i) , j=k 2) (i<=j) or (j<=i) ,j=khow should we interpret the condition given ?