Computer Sciences > GATE 2023 > Theory of Computation
Consider the context-free grammar G below:
S -> aSb | X
X -> aX | Xb | a | b
where S and X are non-terminals, and a and b are terminal symbols. The starting non-terminal is S.
Which one of the following statements is CORRECT?
A
The language generated by G is (a+b)*
B
The language generated by G is a*(a+b)b*
C
The language generated by G is a*b*(a+b)
D
The language generated by G is not a regular language

Explanation

Correct : 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