Teaching UGC NET Mock Test Series 2025 (Paper 1 & 2) Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability
Consider the grammar G given by the production rules:
S → AB | SB | AS | A → a, B → b
where the set of non-terminals are {S, A, B} and the set of terminals are {a,b} What is the number of productions to be used in order to derive a string of terminals of length n?
1
n + 1
2
n2
3
2n - 1
4
2n