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. Several questions in this test are based on it. Here is an example:

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

Sample strings in L : abb, aabb, aabbb

Sample strings NOT in L : aab, ba

Here is the pseudocode that will test whether an input string is in this language or not:

start

while (next input symbol is ‘a’)

push 'a';

while ((next input symbol is ‘b’) && (stack is not empty)

pop;

while ((next input symbol is ‘b’) && (stack is empty)

do nothing;

if ((no more input symbols) && (stack is empty))

accept;

else

reject;

end

I encourage you to manually run through this algorithm for the sample strings provided above and convince yourself that it works properly. If you have any questions, bring it up in Week 6 forum.

Here is another 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 = {anbmcmdn | m,n >= 0, and a, b, c, & d are terminals}

Sample strings in L : abcd, aabcdd, bbcc

Sample strings NOT in L : abbcdd, abdd, aaaaddd

start

while (next input symbol is ‘a’)

[A];

while (next input symbol is ‘b’)

[B];

while ((next input symbol is ‘c’) && (stack top = ‘b’))

[C];

while ((next input symbol is ‘d’) && (stack top = ‘a’))

[D];

if ((no more input symbols) && (stack is empty))

[E];

else

[F];

The answers are as follows:

#1 push input symbol

#2 pop

#3 accept

#4 reject

The Questions are as follows and can be any of the 1-4 answers:                                                                              

A)                                                                                          

B)

C)

D)

E)

F)

Explanation / Answer

ANSWERS:

A) #1. push input symbol // 'a' comes

B) #1. push input symbol // 'b' comes

C) #2. pop // 'c' comes and tack top is 'b'

D) #2. pop   // 'd' comes and tack top is 'a'

E) #3. accept //input empty and stack is also empty

F) #4. reject //input empty but stack not empty

Explanation:

Given langauge is L = {anbmcmdn | m,n >= 0, and a, b, c, & d are terminals}

which means no of char 'a' and 'd' are same also no of char 'b' and 'c' are same. so logic is whenever 'a' comes push into stack and whenever 'd' comes pop from stack. likewise whenever 'b' comes push into stack and whenever 'c' comes pop from stack.

if input is empty and stack is also empty then "accept" if not then reject

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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