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]-[H] in the pseudocode.

L = {anbmcndm | m,n >= 0, and a, b, c, & d are terminals}

Sample strings in L : abcd, aabccd, aacc, abbcdd

Sample strings NOT in L5 : abdd, aaaaddd, abbccd

While the next input symbol is ‘a’

[A];

While the next input symbol is ‘b’

[B];

While the next input symbol is ‘c’

If Queue is empty or front returns ‘b’

[C];

Else

[D];

While the next input symbol is ‘d’

If Queue is empty or front returns ‘a’

[E];

Else

[F];

If (no more input symbols) and (Queue is empty)

[G];

Else

[H];

The answers can one of the following:

#1 addQueue input Symbol

#2 deleteQueue

#3 accept

#4 reject

The questions require one of the answers from 1-4

A)

B)

C)

D)

E)

F)

G)

H)

What is the content of the queue after processing aaaabbbbbcc for the language described in previous question?

Explanation / Answer

[A] 1

[B] 1

[C] 4 reject

[D] 2 delete

[E] 4 reject

[F] 2 delete

[G] 3 accept

[H] 4 reject

aabbbbb will be left in queue.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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