Question 3684 – Theory-of-Computation
December 2, 2023Question 11039 – Linear-Algebra
December 2, 2023Question 5155 – UGC NET CS 2018 JUNE Paper-2
To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is :
Correct Answer: A
Question 35 Explanation:
If all the productions of a grammar are in the form A➝BC OR A➝a then that grammar is said to be in Chomsky normal form.
Example:
S → A B
A → a
B → b
Derive string “ab” from above grammar.
Detailed explanation for example:
Using formula 2 n − 1 ; where n = length of string
2 (2) − 1 = 3
Hence the answer is option(1)
Example:
S → A B
A → a
B → b
Derive string “ab” from above grammar.
Detailed explanation for example:
Using formula 2 n − 1 ; where n = length of string
2 (2) − 1 = 3
Hence the answer is option(1)
2n−1
2n
n+1
n 2