2. Let = {a, b,c}. We know that {w | w {a,b}*} is regular as...

Transcribed Image Text:

2. Let = {a, b,c}. We know that • {w | w€ {a,b}*} is regular as it can be recognized by a FA • {wwR | w € {a,b}*} is context free as it can be recognized by a PDA • {ww | w € {a,b}*} is not context free as it cannot be recognized by a PDA At the same time, we recall that NFAs were generalized to PDAs by adding one stack. Idea: Can PDAs in turn be generalized by adding even more stacks? Suppose we have two stacks, so that the transitions in the state diagram are indicated with b, (c₁, C₂) (e₁, €2), where b is the input symbol read, (c₁, c₂) denote the symbols at the top of the stack 1 and 2, respectively, and (e₁,e2) are symbols pushed back to the corresponding stacks. As before, any of the (b, c1, C2, e1, e2) can be e indicating that the corresponding parameter/operation is omitted. Draw a state diagram for two-stack PDA that recognizes {ww | w € {a,b}*}. Note: consequently, you show that the second stack improves the computational capacity! 2. Let = {a, b,c}. We know that • {w | w€ {a,b}*} is regular as it can be recognized by a FA • {wwR | w € {a,b}*} is context free as it can be recognized by a PDA • {ww | w € {a,b}*} is not context free as it cannot be recognized by a PDA At the same time, we recall that NFAs were generalized to PDAs by adding one stack. Idea: Can PDAs in turn be generalized by adding even more stacks? Suppose we have two stacks, so that the transitions in the state diagram are indicated with b, (c₁, C₂) (e₁, €2), where b is the input symbol read, (c₁, c₂) denote the symbols at the top of the stack 1 and 2, respectively, and (e₁,e2) are symbols pushed back to the corresponding stacks. As before, any of the (b, c1, C2, e1, e2) can be e indicating that the corresponding parameter/operation is omitted. Draw a state diagram for two-stack PDA that recognizes {ww | w € {a,b}*}. Note: consequently, you show that the second stack improves the computational capacity!

Answer rating: 100% (QA)

Creating a state diagram for a twostack PDA that recognizes the language ww w a b involves specifyin... View the full answer