Register

toc cfl or not ?

• retagged by
519 views
2 votes
2 votes

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

• retagged by
User Avatar

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.
User Avatar
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.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
2 answers
1
Anmol Verma asked Dec 2, 2016
713 views
CFL or not TOC
Is L={$a^{n}b^{n}c^{m}$ : n>m} context free...???
Is L={$a^{n}b^{n}c^{m}$ : n>m} context free...???
User Avatar
0 votes
0 votes
0 answers
2
saptarshiDey asked Jan 22, 2019
537 views
A language is cfl or not
L = {a^(p+q) b^(p+q) a^p , p,q>=0} Which one of the following is true about L? L is a regular L is CFL but not regular L is not a CFL
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
User Avatar
2 votes
2 votes
0 answers
3
gari asked Jan 12, 2018
255 views
cfl or not
the condition is 1) (i<=j) or (j<=i) , j=k 2) (i<=j) or (j<=i) ,j=k how should we interpret the condition given ?
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 ?
User Avatar
Link Copied!