LIVE Course for free

Rated by 1 million+ students
Get app now
0 votes
18 views
in Computer by (71.8k points)
closed by

Consider the following languages:

L1 = {abcn+m: m, n ≥ 1}

L2 = {abc2n : n ≥ 1}

Which one of the following is TRUE?

(A) Both L1 and L2 are context-free.

(B) L, is context-free while L2 is not context-free.

(C) L2 is context-free while L1 is not context-free.

(D) Neither L1 nor L2 is context-free.

1 Answer

+1 vote
by (70.8k points)
selected by
 
Best answer

(B) L, is context-free while L2 is not context-free.

L1 → we can rush a’s & b’s and for each c we can pop one item from stack, one c’s are over stack should be empty.

∴ = L1 CFL 

For L2, we can’t build PDA [a’s & b’s should be equal & C′ should be double of that count]

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam, ICSE Board Exam, State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.

Categories

...