Problem with understanding Push down Automata Eq from the book

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
I have problem in understanding following eq of Push down automata from the book:

L= {a^n b^n: n>=0} U {a}

I am able to understand, when we push 'a', then '1' would be stored in the stack. And when we pop 'a' from the stack then 1' is removed from the stack.
This helps to keep track of the fact that count of 'a' and 'b' is equal.

But why the above equation only show addition operation and not the removal operation.

Zulfi.
 

WBahn

Joined Mar 31, 2012
29,976
You are confusing numerous things.

L= {a^n b^n: n>=0} U {a}

is nothing more than the definition of a language, which is a set of strings, by describing the strings that are in that language. It doesn't say anything about stacks and pushes and pops or anything else about the machine that recognizes that language.

In this case, the language is the union of two sets of strings. The first set consists of all strings containing a number of a's followed by the same number of b's (which includes the empty string since it can be described as zero a's followed by zero b's). The second set consists of the string "a" and nothing else. The language consists of all strings that are in one or both of these two sets.

Saying "when we push 'a', then '1' would be stored on the stack" is nonsensical; what gets stored on the stack is whatever we push onto it -- that is what it means to "push" something. Similarly, if we pop 'a' from the stack, then that means that the stack had an 'a' on the top of it and we removed that 'a' from the stack.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
You are confusing numerous things.

L= {a^n b^n: n>=0} U {a}

is nothing more than the definition of a language, which is a set of strings, by describing the strings that are in that language. It doesn't say anything about stacks and pushes and pops or anything else about the machine that recognizes that language.

In this case, the language is the union of two sets of strings. The first set consists of all strings containing a number of a's followed by the same number of b's (which includes the empty string since it can be described as zero a's followed by zero b's). The second set consists of the string "a" and nothing else. The language consists of all strings that are in one or both of these two sets.
Thanks.
Saying "when we push 'a', then '1' would be stored on the stack" is nonsensical; what gets stored on the stack is whatever we push onto it -- that is what it means to "push" something. Similarly, if we pop 'a' from the stack, then that means that the stack had an 'a' on the top of it and we removed that 'a' from the stack.
I have added the image of book's contents. Pdna ia reading a string, and if the character is 'a' it stores '1' in the stack and if the character is 'b', it removes '1' from the stack.
I have attached images of the book in the word file attached. Kindly check if am right or not and based upon that "U {a}" is okay or not.

Zulfi.
 

Attachments

WBahn

Joined Mar 31, 2012
29,976
Thanks.


I have added the image of book's contents. Pdna ia reading a string, and if the character is 'a' it stores '1' in the stack and if the character is 'b', it removes '1' from the stack.
I have attached images of the book in the word file attached. Kindly check if am right or not and based upon that "U {a}" is okay or not.

Zulfi.
Be sure that you understand that "reading a string" is not the same as "pushing".

Does that machine recognize the string "a"?

If not, then it doesn't recognize the language you are trying to implement.

Since that machine recognizes L= {a^n b^n: n>=0}, do you expect that it would recognize the string "a"?
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Be sure that you understand that "reading a string" is not the same as "pushing".

Does that machine recognize the string "a"?

If not, then it doesn't recognize the language you are trying to implement.

Since that machine recognizes L= {a^n b^n: n>=0}, do you expect that it would recognize the string "a"?
As far I understand, it is reading the string like aaabbb, i think from left but the book says it reads from right (but my prof. started from 'a'). And then for every 'a', we pushed '1' and every 'b' we popped '1'. This means that it recognizes both the sub string "a" and the sub string "b". That's why it makes sure that "a"s and "b's should be of equal length.

But the equation only performs the union of "a" and does not consider "b".

If you have time kindly read the book content, I have attached, otherwise, I have to skip this part.

Zulfi.
 

WBahn

Joined Mar 31, 2012
29,976
As far I understand, it is reading the string like aaabbb, i think from left but the book says it reads from right (but my prof. started from 'a').
You need to read what it says a lot more closely. It says, "In our notation we assume that the insertion of string into a stack is done symbol by symbol, starting at the right end of the string."

And then for every 'a', we pushed '1' and every 'b' we popped '1'. This means that it recognizes both the sub string "a" and the sub string "b". That's why it makes sure that "a"s and "b's should be of equal length.
Correct. THAT machine recognizes strings that consist of some number of a's followed by that same number of b's.

But the equation only performs the union of "a" and does not consider "b".
So?

The language you are working with is the union of two sets. Do you understand what the union of two sets means?

If I have a language consisting of all mammals and I union it with a set containing a frog, I know of a set that contains all mammals and a frog.

Your language consists of the string "a" and all of the strings having some number of a's followed by that same number of b's.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
You need to read what it says a lot more closely. It says, "In our notation we assume that the insertion of string into a stack is done symbol by symbol, starting at the right end of the string."
I have read that line. But for a string "aaabbb", if the machine reads from right-end then it would get 'b' first, this is one confusion.

Correct. THAT machine recognizes strings that consist of some number of a's followed by that same number of b's.
So if it reads 'b' first then we dont have the string: number of a's followed by that same number of b's as you are saying.
So?

The language you are working with is the union of two sets. Do you understand what the union of two sets means?


Your language consists of the string "a" and all of the strings having some number of a's followed by that same number of b's.
Yes.

If I have a language consisting of all mammals and I union it with a set containing a frog, I know of a set that contains all mammals and a frog.
This would look different from our initial string where we have number of 'a's is equal to number of 'b's. Why we want to do that?

Thanks a lot for your time.

Zulfi.
 
Last edited:

WBahn

Joined Mar 31, 2012
29,976
I have read that line. But for a string "aaabbb", if the machine reads from right-end then it would get 'b' first, this is one confusion.
You still are not reading what it says!

It says NOTHING about reading the INPUT string from right to left.

It says that you when you want to INSERT A STRING ONTO THE STACK, that you push the character of THAT string from right to left.

This is nothing more than a notational convenience.

By the basic definition of a PDA, each transition gets to push at most one character onto the stack. But sometimes we want to push several characters onto the stack (such as the rule they have where they push "11" onto the stack). Strictly speaking we would need a state for each character in the string in which each transition rule after the first one would be an epsilon transition (reading nothing from the input string and popping nothing from the stack) and pushing the another character onto the stack. To make the diagram simpler, we eliminate the additional states and show the first transition rule as pushing a string instead of a single character onto the stack. But we have to specify what order the characters in that string get pushed onto the stack -- left-to-right or right-to-left. The normal convention is right-to-left because this places the first character in the string at the top of the stack when we are finished and it turns out that this is what we will want to have happen when we push grammar productions onto the stack, so this convention let's us write our transition rules so that they push productions onto the stack that are written they same way that they are in the grammar (instead of us having to reverse them all, which is a recipe for disaster).

This would look different from our initial string where we have number of 'a's is equal to number of 'b's. Why we want to do that?
Why do we want a language in which we have some number of a's followed by the same number of b's? Who knows? It doesn't matter! That is the language that has been defined and that we need to design a machine to recognize. If someone wants/needs to define a DIFFERENT language that happens to consist of all of the strings in the first one plus a string that is an 'a' all by itself, we don't need to know why they wanted or needed to do that -- we have to design a machine that recognizes it (or determine that doing so is not possible).
 
Top