GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
76 views

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

asked in Theory of Computation by Veteran (20.2k points)   | 76 views
it is CFL ryt ?
two comparison i<j and j<k ..not cfl
k got now thank u :)

1 Answer

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.
answered by Active (1.5k points)  


Top Users Jun 2017
  1. Bikram

    3704 Points

  2. Arnab Bhadra

    1502 Points

  3. Hemant Parihar

    1502 Points

  4. Niraj Singh 2

    1481 Points

  5. junaid ahmad

    1432 Points

  6. Debashish Deka

    1402 Points

  7. Rupendra Choudhary

    1230 Points

  8. rahul sharma 5

    1222 Points

  9. Arjun

    1168 Points

  10. pawan kumarln

    1164 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 26 - Jul 02
  1. pawan kumarln

    296 Points

  2. akankshadewangan24

    214 Points

  3. Arjun

    208 Points

  4. Debashish Deka

    156 Points

  5. Hira Thakur

    130 Points


23,414 questions
30,125 answers
67,509 comments
28,443 users