Computer Sciences > Gate 2022 > 1

Contributed by: Dr. Sarah Chen

Report Correct Copyright Claim

Consider the following languages:

L1 = {ww | w ∈ {a, b}* }
L2 = {aⁿbⁿcⁿ | m, n≥ 0}
L3 = {a^mbⁿcⁿ | m, n≥ 0}

Which of the following statements is/are FALSE?

A

L1 is not context-free but L2 and L3 are deterministic context-free.

B

Neither L1 nor L2 is context-free.

C

L2, L3, and L2 ∩ L3 all are context-free.

D

Neither L1 nor its complement is context-free.

Check Answer

Explanation

Correct : b,c,d

Similar Questions

What is the worst-case time complexity of insertion in an AVL tree?

Question #23 Medium

Which operations on a binary search tree have O(h) complexity?

Question #31 Easy

Compare search complexities of sorted array vs balanced BST.

Question #47 Hard

Related Topics

Data Structures Binary Search Tree Time Complexity Algorithm Analysis Tree Algorithms Computer Science