retagged by
2,661 views
11 votes
11 votes
Consider the folllowing grammar

$ S\rightarrow AaS \ |\ b$

$ A\rightarrow c \ |\ d \ |B$

$ B\rightarrow AgC \ |\ AhC \ | \ DgC | \ DhC$

$C\rightarrow c \ |\ d \ | \ D$

$ D\rightarrow eBf$

 

Which of the following are  viable prefix ?

$ \left ( 1 \right )Aab$

$ \left ( 2 \right )ca$

$ \left ( 3 \right )cab$

$\left ( 4 \right )AgCS$
retagged by

2 Answers

Best answer
21 votes
21 votes

A viable prefix is -->

  • A string that equals a prefix of right-sentential form upto and even including its unique handle .
  • And also any prefix of a string that satisfies first.


A). S -> AaS -> Aab  (Bold is used to show handle at each step)

  • Viable prefix = {Ɛ,A,Aa,Aab,AaS} 

B). S -> AaS -> Aab -> cab   (Bold is used to show handle at each step)

  • Viable prefix = {Ɛ,A,c,Aa,Aab,AaS} 

C). Same as B).

D). S -> AaS -> Aab -> Bab -> AgCab  (Bold is used to show handle at each step)

  • Viable prefix = {Ɛ,A,B,Aa,Aab,AaS,Ag,AgC} 
selected by
2 votes
2 votes
stack content at any time is called viable prefix

Aab is a viable prefix.

ca can't be viable prefix as after c put in stack before inserting a c will reduce to A

cab also can't be viable prefix reason is same as for ca

AgCS is also not a viable prefix reson S can't be push in stack S is not a symbol in given grammar.

so ans :-option a

Related questions

3 votes
3 votes
1 answer
1
0 votes
0 votes
2 answers
2
dhruba asked Jun 5, 2023
314 views
0 votes
0 votes
2 answers
3
Rajesh R asked Nov 6, 2017
1,428 views