Discussion
Consider the following grammar \(G\), with \(S\) as the start symbol. The grammar \(G\) has three incomplete productions denoted by (1), (2), and (3).
\(S \to daT\ |\) ___(1)___
\(T \to aS\ |\ bT\ |\) ___(2)___
\(R \to\) ___(3)___ \(|\ \epsilon\)
The set of terminals is \(\{a, b, c, d, f\}\). The FIRST and FOLLOW sets of the different non-terminals are as follows.
FIRST(\(S\)) = \(\{c, d, f\}\), FIRST(\(T\)) = \(\{a, b, \epsilon\}\), FIRST(\(R\)) = \(\{c, \epsilon\}\)
FOLLOW(\(S\)) = FOLLOW(\(T\)) = \(\{c, f, \$\}\), FOLLOW(\(R\)) = \(\{f\}\)
Which one of the following options CORRECTLY fills in the incomplete productions?
Answer: A
The productions are (1) \(S \to Rf\) (2) \(T \to \epsilon\) (3) \(R \to cTR\).
Check them against the given sets. FIRST(T) contains \(\epsilon\), so T needs an \(\epsilon\) production: \(T \to \epsilon\), which rules out \(T \to cT\) (that would put c in FIRST(T)). FIRST(S) = {c, d, f}: d comes from daT, and \(S \to Rf\) adds FIRST(R) = {c} plus f because R is nullable. \(S \to fR\) would give only {d, f}.
With \(R \to cTR\): FIRST(R) = {c, \(\epsilon\)}; FOLLOW(R) = {f} from \(S \to Rf\); and FOLLOW(T) gets c from the R after T and, since R is nullable, FOLLOW(R) = {f}, while \(S \to daT\) and \(T \to aS\) make FOLLOW(T) = FOLLOW(S) = {c, f, \$}. Every given set matches, so the first option is the one that fits.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development