Consider the following languages:L1= {0n1n n ≥ 0}L2= {wcwr wε {a, b}&lowast;}L3= {wwr wε{a, b}&lowast;}Which of these languages are deterministic context-free languages?a)Only L1b)Only L1 and L2c)None of the languagesd)All three languagesCorrect answer is option 'D'. Can you explain this answer?

Question

Consider the following languages:L1= {0n1n n &ge; 0}L2= {wcwr  w&epsilon; {a, b}&lowast;}L3= {wwr  w&epsilon;{a, b}&lowast;}Which of these languages are deterministic context-free languages?a)Only L1b)Only L1 and L2c)None of the languagesd)All three languagesCorrect answer is option 'D'. Can you explain this answer?

Answer

Given,

L₁= {0ⁿ1ⁿ∣ n ≥ 0}

Languages L₁ contains all strings in which n0's are followed by n1's.

Deterministic PDA can be constructed to accept L₁. For 0's we can push it on stack and for 1's, we can pop from stack. So, it is DCFL.

L₂= {wcwr ∣ wε{a, b}^∗}

L₂contains all strings of form wcwr where w is a string of a's and b's and wr is reverse of w.

For example, aabbcbbaa. To accept this language, we can construct PDA which will push all symbols on stack before c.

After c, if symbol on input string matches with symbol on stack, it is popped.

So, L₂ can also be accepted with deterministic PDA, thus, it is also DCFL.

L₃= {wwr ∣ wε{a, b}^∗}

L₃ contains all strings of form wwr where w is a string of a's and b's and wr is reverse of w.

But we don't know where w ends and wr starts. For example, aabbaa is a string corresponding to L₃. For first a, we will push it on stack.

Next a can be either part of w or wr where w = a.

Therefore, there can be multiple moves from a state on an input symbol.

So, only non-deterministic PDA can be used to accept this type of language.

So, it is NCFL, not DCFL.

Thus, all three languages are deterministic context-free languages.

Hence, the correct option is (D).

Answer

L1 is the language that consists of strings of the form 0n1n, where n is a non-negative integer. In other words, L1 contains strings that start with some number of 0's followed by an equal number of 1's.

Examples of strings in L1 include: '', '01', '0011', '000111', '00001111', etc.

Some strings that are not in L1 include: '01', '0', '1', '0001111', '000001111', etc.

L1 can be described by the regular expression 0*1*, which means zero or more 0's followed by zero or more 1's.

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company