Option c and d are same right? :o

The Gateway to Computer Science Excellence

0 votes

L1 = {a^mb^nc^p | m ≥ n or n = p}

L2 = {a^mb^nc^p | m ≥ n and n = p}

(a) Both are NCFL’s

(b) L1 is DCFL and L2 is NCFL

(c) L1 is NCFL and L2 is not context-free

(d) Both are not context-free

Solution: Option (c)

how it is possible plz explain indetail

L2 = {a^mb^nc^p | m ≥ n and n = p}

(a) Both are NCFL’s

(b) L1 is DCFL and L2 is NCFL

(c) L1 is NCFL and L2 is not context-free

(d) Both are not context-free

Solution: Option (c)

how it is possible plz explain indetail

0

option c says L1 is non determinstic context free language and L2 is determinstic cfl

option d says both L1 and L2 are non cfl

option d says both L1 and L2 are non cfl

0

L1 requires only one comparission at a time ===>CFL, due to Ambiguity it is Non-Deterministic CFL

L2 requires two comparissions at a time ===> CSL

+1

There are two possibilities

1) m>=n 2) n=p

For 1) first push a then pop 1 a for each b. Since m>=n so it might happen that there are still some a's left after all b's are exhausted.

For the remaining c's we don't need to do anything

For 2) Do nothing when we get a and push all b's and pop each b for each c.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,324 answers

198,404 comments

105,169 users