$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$

The Gateway to Computer Science Excellence

+2 votes

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

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

- Only (i)
- Only (ii)
- Only (i) and (ii)
- (i), (ii) and (iii)

0 votes

Answer is D.

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 shiftreduce 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:**

0 votes

A viable prefix is a legitimate prefix that could lead to a handle.

Since handle will always be found on top of the stack, all the viable prefixes of it can appear below it in the stack. If handle is not found yet, the stack would contain just viable prefixes.

I is true.

Viable **prefix** can't extend past the handle. That's why it's a prefix!

II is true.

The set of all viable prefixes of a language is a Regular Language, so it can be recognised by a DFA.

III is true.

**Option D**

52,345 questions

60,514 answers

201,932 comments

95,365 users