Grammar
Question 1 |
Which of the following conversions is not possible (algorithmically)?
Regular grammar to context free grammar | |
Non-deterministic FSA to deterministic FSA | |
Non-deterministic PDA to deterministic PDA | |
Non-deterministic Turing machine to deterministic Turing machine |
Question 1 Explanation:
NPDA to DPDA conversion is not possible. They have different powers.
Question 2 |
In the following grammar
X ::= X ⊕ Y/Y
Y ::= Z * Y/Z
Z ::= id
Which of the following is true?
‘⊕’ is left associative while ‘*’ is right associative | |
Both ‘⊕’ and ‘*’ is left associative | |
‘⊕’ is right associative while ‘*’ is left associative | |
None of the above |
Question 2 Explanation:
⊕ is left associative.
* is right associative.
Question 3 |
A grammar that is both left and right recursive for a non-terminal, is
Ambiguous | |
Unambiguous | |
Information is not sufficient to decide whether it is ambiguous or unambiguous | |
None of the above |
Question 3 Explanation:
If a grammar is both left and right recursion, then grammar may or may not be ambiguous.
There are 3 questions to complete.