Stacks and queues can be used for determining whether a particular input string

Question

Stacks and queues can be used for determining whether a particular input string is in the language or not. Here is a language and the pseudocode for recognizing whether the input string is in the language or not. Choose an appropriate action for each place-holder [A]-[F] in the pseudocode.

L = {(a+b)* | a and b are terminals and string has equal number of a’s and b’s}

Sample strings in L : ab, ba, abab, abba, baad, bbbaaa

Sample strings NOT in L : a, b, abb, aab, aabbb, ababa, babab, bbaaa

start

while (there are more input symbols)

if (next input symbol is ‘a’)

if (stack top is ‘a’) or (stack is empty)

[A];

else

[B];

else

if (stack top is ‘b’) or (stack is empty)

[C];

else

[D];

if (stack is empty)

[E];

else

[F];

end

The answers can be one of the following:

#1 push input symbol

#2 pop

#3 accept

#4 reject.

The questions need one of the answers from 1-4

A)

B)

C)

D)

E)

F)

What is the content of the stack after processing abaaababb for the language described in previous question?

Explanation / Answer

[A] - Push

[B] - Pop

[C]- Push

[D] - Pop

[E] - accept

[F] - reject

the content of the stack will be a after processing the given string.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.