+1 vote
146 views

Which of the following sentences regarding Viable prefixes is/are CORRECT?

1. Viable prefixes is the set of prefixes of right-sentential forms that can appear on the stack of a shift-reduce parser
2. Viable prefixes is the set of prefixes of right-sentential forms that do not extend past the end of the right-most handle
3. Viable prefixes can be recognized using a DFA

1. Only (i)
2. Only (ii)
3. Only (i) and (ii)
4. (i), (ii) and (iii)
| 146 views
+4
$D$.

$I$ and $II$ is the definition of viable prefixes.

The set of viable prefixes for any grammar is a regular language so can be recognized by a $DFA$
0
Please provide some references for above statements.
0

I : Definition of viable prefix -

Viable prefixes are the prefixes of right sentential forms that do not extend beyond the end of its handle.

i.e. a viable prefix either has no handle or just one possible handle on the extreme RIGHT which can be reduced.

II :  Definition of viable prefix -

viable prefixes are the set of prefixes of right sentential forms that can appear on the stack of a shift­reduce parser

III :The set of all viable prefixes of a context-free language is a REGULAR LANGUAGE. i.e., viable prefixes can be recognized by using a FINITE AUTOMATA.

So I, II & III are true.

References:

by Junior (887 points)