Which of the following NFA is valid for the given DFA?
(a) 
(b) 
(c) 
UGC NET Computer Science Compiler Design Previous Year Questions (PYQs)
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations
Study Stuff for MCA Examinations
Arrange the following parsers in increasing order of their power (least → most):
- LR(0)
- LR(1)
- LALR(1)
- LL(0)
- SLR
1
2
3
4
Solution
- LL(0) is the weakest (no lookahead, top-down).
- LR(0) is stronger than LL(0) (bottom-up, no lookahead).
- SLR(1) adds 1-symbol lookahead using FOLLOW sets → accepts more grammars than LR(0).
- LALR(1) merges LR(1) states; more powerful than SLR(1) but below LR(1).
- LR(1) is the most powerful among these deterministic bottom-up parsers.
Consider the following DFA that generates set of strings over Σ = {a, b, c}.
Identify the best description of the language for the DFA.
1
2
3
4
Solution
The automaton has two “phases” connected by the path recognizing a→b→c. Each time the substring “abc” is seen, the DFA moves to the other phase, toggling parity. The start phase (no “abc” yet) is accepting (count 0), and after every additional “abc” the parity flips; therefore the accepting states correspond to an even number of occurrences of “abc”. Options 1 and 2 describe Σ* (all strings), and option 3 does not match the transitions.
Match List I with List II
| List I (Grammar Type) | List II (Production Form) |
|---|---|
| A. Type 3 Grammar | IV. $V \rightarrow V\Sigma \mid \Sigma$ |
| B. Type 2 Grammar | I. $V \rightarrow (V \cup \Sigma)^{*}$ |
| C. Type 1 Grammar | II. $\lambda A \beta \rightarrow \lambda\,\gamma\,\beta,\;(\lambda,\beta)\in (V\cup\Sigma)^{*}$ |
| D. Type 0 Grammar | III. $(V\cup\Sigma)^{*} \rightarrow (V\cup\Sigma)^{*}$ |
1
2
3
4
Solution
Why: Type-3 (regular) → right-linear (IV); Type-2 (context-free) → $V \to (V\cup\Sigma)^*$ (I); Type-1 (context-sensitive) → context-preserving form (II); Type-0 (unrestricted) → any string to any string (III).
Which of the following Grammars is/are only Context-Free?
| Label | Productions | Note |
|---|---|---|
| A | S → Ab aS → aA A → a | LHS “aS” has a terminal → not CFG |
| B | S → Ab A → Sa A → a | All rules are left-linear (V→Vt or V→t) → regular |
| C | S → AS S → aA A → a | CFG, not regular (non-linear: V→VV) |
| D | S → Ab S → aA A → a | CFG; mixes left/right-linear → not regular |
| E | S → Sb A → Aa A → ε | From start S no terminal string → L(S)=∅ (regular) |
1
2
3
4
Solution
A is not even CFG (terminal on LHS).
B is a regular (left-linear) grammar.
C and D are context-free but not regular (“only” context-free).
E generates the empty language from start symbol S, which is regular.
UGC NET Computer Science
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
UGC NET Computer Science
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Ask Your Question or Put Your Review.
