[senorfletch]

Spoiler

Spoiler

Hello,

Above are two examples of pushdown automata. I'm trying to make sense of how the stack works with a step by step process of an actual string in the language. The first attachment is an example of how I'm trying to do this, I see one mistake already(I think q6 should be included in current states for #3) but I think it's a good example of the kind of explanation I would like for the next example. I've been trying several different ways of conceptualizing how example 2.18 works but it seems no matter what I do I expect the machine to push whatever is read at the input(0 or 1) and then if the input=stack, pop. In other words the stack either gets larger(input=/=stack) or stays the same size(input=stack). The author's informal description of the machine does nothing to help me understand how the machines processes an actual string step by step.(Both of these examples are from the text Introduction to the Theory of Conputation by Sipser). Below is a quote from the text:

"Begin by pushing the symbols that are read onto the stack. At each point nondeterministically guess that the middle of the string has been reached and then change into popping off the stack for each symbol read, checking to see that they are the same. If they were always the same symbol and the stack empties at the same time as the input is finished, accept; otherwise reject."

I think ok, maybe you can only read one input symbol at a time but you can perform many stack operations as long as they're satisfied by conditions on arrows(transition function). But then I do not understand why the input symbol from q2 isn't pushed indefinitely. It's not explained at all well in the book. I suppose if someone could point out the error in my description of the computation of string 1001(this example accepts strings of form ww^R, where w^R is the reverse of the string w) by M3 and correct it for me that would greatly help.

1. Start at q1. Goto q2,q3(through q2) push $
2. Input:1001 Stack: $
q2: read 1 ---> push 1 Stack: 1$ q2--->q2,q3
q3: read 1 ---> (since input=1 AND stack=1) pop 1 stack: $ q3--->q3
GOTO NEXT INPUT
Now my understanding is we take all states with arrows pointing to them(q2,q3) to be the current states
3. Input: 1001 Stack: $
q2: read 0 ---> push 0 Stack: 0$ q2--->q2,q3
q3: read 0 ---> pop 0 Stack: $ q3--->q3
GOTO NEXT INPUT
4. Input: 1001 Stack: $
q2: read 0 ---> push 0 Stack: 0$ q2--->q2,q3
q3: read 0 ---> pop 0 Stack: $ q3--->q3
GOTO NEXT INPUT
5. Input: 1001 Stack: $
q2: read 0 ---> push 0 Stack: 0$ q2--->q2,q3
q3: read 0 ---> pop 0 Stack: $ q3--->q3


There are obviously some problems with this. For one I left out that q3--->q4 when stack=$, also I haven't read anything yet that says I should process q2 before q3, and the results are different if I do q3 first. And also the way I'm doing it ALL strings will be accepted by this machine because we always get stack=$ at the end of each step so q3--->q4, so I'm doing it wrong. The epsilons in this example really have me confused. Any help would be appreciated.

This post has been edited by macosxnerd101: 21 April 2015 - 08:23 AM
Reason for edit:: Added spoiler tags for large images- Please don't undo my edit. The images took a while to load for me due to their size. The spoiler tag helps folks with this.

[macosxnerd101]

In example 2.18 from Sipser, the PDA is non-deterministic. The PDA isn't powerful enough to determine the length of the string a priori. So it needs to guess where to split it. Note that a string is accepted by a non-deterministic automaton if there exists an accepting computation.

So for L = {ww^{R} : w \in \{0, 1\} }, we push characters onto the stack and have the option to pop them off when we find a matching character (hence, the non-determinism).

So for 1001, we have the following computation:
-Push 1 onto the stack
-Push 0 onto the stack
-Read in the second 0 and pop 0 from the stack
-Read the second 1 and pop 1 from the stack.

Accept 1001 because the stack is empty upon termination of the algorithm.

[senorfletch]

macosxnerd101, on 21 April 2015 - 08:22 AM, said:

In example 2.18 from Sipser, the PDA is non-deterministic. The PDA isn't powerful enough to determine the length of the string a priori. So it needs to guess where to split it. Note that a string is accepted by a non-deterministic automaton if there exists an accepting computation.

So for L = {ww^{R} : w \in \{0, 1\} }, we push characters onto the stack and have the option to pop them off when we find a matching character (hence, the non-determinism).

So for 1001, we have the following computation:
-Push 1 onto the stack
-Push 0 onto the stack
-Read in the second 0 and pop 0 from the stack
-Read the second 1 and pop 1 from the stack.

Accept 1001 because the stack is empty upon termination of the algorithm.

Could you please elaborate in terms of state transitions as I gave in the examples?
The initial state is q1. Goes to state q2 because of rule epsilon,epsilon--->$(pushes $ onto the stack). Also q3 is another state after going from q2---->q3 because of rule epsilon,epsilon---->epsilon.

When we read the first input symbol 1, there is a choice to read from q3 or q2 correct? How do we chose which to do first or am I looking at this wrong? Also I thought the machine accepts because of the end state not because the stack is empty? In the formal definition of pushdown automaton Spiser gives "3. condition states that an accept state occurs at input end." I'm having a hard time understanding what the currents states are and how they interact with the stack.

[macosxnerd101]

The PDA state a, b -> c says that when you read in a, you may replace b with c as the top of the stack. Note that a, b, c \in \Sigma U { \epsilon }.

So state 1 to state 2 initializes the stack. At state 2, if we read 0 or 1, we push that character onto the stack. The state 2 to state 3 transition is non-deterministic, not changing anything. Then at q3, we pop from the stack. We can only transition to state 4 from state 3 if there are no characters on the stack.

Quote

When we read the first input symbol 1, there is a choice to read from q3 or q2 correct?

These are states. We aren't reading from them.

Quote

How do we chose which to do first or am I looking at this wrong?

You can only transition states where there is a directed edge on the graph diagram.

Quote

Also I thought the machine accepts because of the end state not because the stack is empty?

We will terminate at an accept state if and only if the stack is empty.

Quote

Could you please elaborate in terms of state transitions as I gave in the examples?

Based on my explanations, give it a try.

[senorfletch]

Well ok, I find this very hard to explain. The fact that this is nondeterministic means that we can transition to a set of states. That's how I'm interpreting it anyways.

So when I say how do we choose which state to read the input symbol from, consider your statement
"At state 2, if we read 0 or 1, we push that character onto the stack"
So before we read an input we have a set of current states that we are at correct? States q2 and q3 after pushing $ onto the stack? At q3 we may read a 0 at the input, a 0 at the top of the stack, and if both are present we pop the 0. At q2 we read the symbol at push it on to the stack. If there's no stack, nondeterminism hasn't been very confusing for me. If you look at the first attachment I try to show how I represent the states we are at to determine how the machine processes the string.

This post has been edited by senorfletch: 21 April 2015 - 09:06 AM
Reason for edit:: No need to quote the post above

[macosxnerd101]

Try parsing 1001 again.

We proceed as follows:

• Start at q1 and initialize the stack. Proceed to q2.
  
• At q2, we read in the first character, which is 1. So we push it onto the stack.
  
• At q2, we read in the second character, which is 0. So we push it onto the stack.
  
• We apply the \epsilon transition to move to q3. We do not modify the stack.
  
• We read in the second 0 at q3. Since 0 is at the top of the stack, we pop 0. (If 0 was not at the top of the stack, we would reject the string).
  
• We read in the second 1 at q3. Since 1 is at the top of the stack, we pop it.
  
• Proceed to q4 with the \epsilon transition and accept the string.

We could have the following computation instead, which does not result in accepting the string:

• Start at q1 and initialize the stack. Proceed to q2.
  
• At q2, we read in the first character, which is 1. So we push it onto the stack.
  
• At q2, we read in the second character, which is 0. So we push it onto the stack.
  
• At q2, we read in the third character, which is 0. So we push it onto the stack.
  
• At q2, we read in the fourth character, which is 0, so we push it onto the stack.
  
• We apply the \epsilon transition to move to q3. There are no more characters to parse, so we reject the string.

Recall the definition of string acceptance with non-deterministic automata: there must exist an accepting computation. This is not a universal quantifier.

Quote

The fact that this is nondeterministic means that we can transition to a set of states.

Formally, yes. Intuitively, we have choice. We transition to a single state, which we pick from the set of possible states.

[senorfletch]

I think the easiest way to make sense of this is to ask if we could write a program that computes the PDA. Where each state is a variable, q1,q2,q3 and q4. If we are at one of these states, say q1 we say q1=1, if not q1=0.
Maybe something similar to this(this is what I tried before when I gave up)

INPUT() and STACK() are indexed arrays
[initialize states]
q1,q2,q3,q4=0
index=1
stack index=1
q1=1
start loop(while INPUT(index)=/=empty)
[define transition rules]
if q1==1
{
q2=1,STACK(stackindex)=$, stackindex=stackindex+1, STACK(stackindex)=1[PUSH]
}

if q2==1
{
if INPUT(index)==0
{
q2=1,push 0
}

if INPUT(index)==1
{
q2=1,stackindex=stackindex+1, STACK(stackindex)=1[PUSH]
}

q3=1
}

if q3==1
{
if INPUT(index)==0 AND STACK(stackindex)==0
{
STACK(stackindex)=empty, stackindex=stackindex-1, q3=1[POP]
}

if INPUT(index)==1 AND STACK(stackindex)==1
{
STACK(stackindex)=empty, stackindex=stackindex-1, q3=1[POP]
}

if STACK(stackindex)=$
{
q4=1
}
}
[goto next input symbol]
index=index +1
end loop
if q1==1 OR q4==1
{
ACCEPT=TRUE
}
else
ACCEPT=FALSE

END PROGRAM

I don't think this program is correct but could you write a similar program that determines whether or not a string is accepted by the PDA?

EDIT: Just realized I'd have to add conditions to set q's to 0 if the conditions are not met.

This post has been edited by macosxnerd101: 21 April 2015 - 09:49 AM
Reason for edit:: Please STOP quoting large posts

[macosxnerd101]

First, please stop quoting the post right above you, especially when it is a large post. If you scroll all the way down, there is a Reply button. You can use that instead of the Quote + Reply button.

Quote

I don't think this program is correct but could you write a similar program that determines whether or not a string is accepted by the PDA?

I think you can crank out a Java program or something similar using a stack to check if a string is a palindrome. That's really all the PDA is doing.

I've already walked through two possible computations for the same string in the PDA. If there are questions on how it works, I'm happy to field them. But I'm not really interested in writing a program to do this.

[senorfletch]

Sorry about that. You don't have to write the program but if you could explain how the "guessing" part of the program might work that would be very helpful. The explanation you gave was based on your prior knowledge of the string and does not explain how the machine actually works. Does the program work by holding the original stack in it's memory, guessing it's at the middle for every new input, then if it's not return to the original stack? The addition of the stack and how it is handled is very confusing for me.

[macosxnerd101]

Quote

Recall the definition of string acceptance with non-deterministic automata: there must exist an accepting computation. This is not a universal quantifier.

Note the definition of string acceptance in non-deterministic automata again.

Quote

The explanation you gave was based on your prior knowledge of the string and does not explain how the machine actually works.

I gave two possible computations for the same string. One accepts and one doesn't. There are many other non-accepting computations for 1001. I'm not enumerating them- you can do that if you want.

Quote

Does the program work by holding the original stack in it's memory, guessing it's at the middle for every new input, then if it's not return to the original stack?

I would not think of it as backtracking. It's literally this: we have a bunch of configurations for an input string. Does one of them result in the string being accepted? Non-deterministic automata have a second alphabet \Gamma, which generate a choice string. The choice string characters combined with the input characters determine the input. The choice string is generated by some mechanism somewhere. You can equivocally think of the choice string as the walk for the input string to follow.

You are driving down a road. There is a fork in the road, both sections labeled a. You can choose right or left. One of them takes you to your destination and the other takes you off a cliff. Does there exist a path from your starting location to the destination? The answer is yes. This is all there is to non-deterministic automata.

Also, perhaps this read on the Usefulness of Non-Determinism will be a good read.

Quote

The addition of the stack and how it is handled is very confusing for me.

The stack shouldn't be confusing. If you don't understand non-determinism, it might be useful to revisit this concept with non-deterministic finite state automata before proceeding to PDAs.

[senorfletch]

I think I understand. The author has not talked about a gamma alphabet yet, I was able to understand how to represent actual examples of strings and determine whether or not they were accepted by a NFA by keeping track of the set of states, all of the possible choices that could be made from the epsilons, and determining if a string is accepted by the NFA if any state in the current states at the end of the string is an accept state.

Correct me if I'm wrong but I think the mistake I'm making is not taking into account that for each of these choices there is a unique stack associated with that choice. So unlike NFA I cannot simply collect a set of states and determine if the string is accepted if in one of these states. I'd have to have a unique stack for each choice I made. Thanks for your patience and your help.