Computer Sciences > Gate 2016 Set-1 > CGF

Contributed by: Dr. Sarah Chen

Report Correct Copyright Claim

Consider the following context-free grammars:

G1: S → aS|B, B → b|bB
G2: S → aA|bB, A → aA|B|ε, B → bB|ε

Which one of the following pairs of languages is generated by G1 and G2, respectively?

A

{a^mbⁿ |m > 0 or n > 0} and {a^mbⁿ |m > 0 and n > 0}

B

{a^mbⁿ |m > 0 and n > 0} and {a^mbⁿ |m > 0 or n ≥ 0}

C

{a^mbⁿ |m ≥ 0 or n > 0} and {a^mbⁿ |m > 0 and n > 0}

D

{a^mbⁿ |m ≥ 0 and n > 0} and {a ^mbⁿ |m > 0 or n > 0}

Check Answer

Explanation

Correct : CGF

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