Lucy
Lucy

Reputation: 491

Push Down Automanton-Computation

I am trying to understand how PDA works. In the following diagram I understand how transition functions work and how the stack must be updated. But The only question I have is Why the Start state is an accept state as well? while the PDA is for L = {on1n | n ≥ 0}, means it must not accept an empty string. Can some one explain the reason for making the start to be accept state, please?

enter image description here

Upvotes: 0

Views: 105

Answers (2)

Joshua Swain
Joshua Swain

Reputation: 690

Because the NFA accepts empty strings

Upvotes: 0

uba
uba

Reputation: 2031

L = {0n1n | n ≥ 0}

When n=0, the string is:

0010 = zero 0's followed by zero 1's which is the empty string. So according to the definition, the language L does include the empty string.

If it were to not accept the empty string, the definition would be:

L = {0n1n | n > 0}

Upvotes: 0

Related Questions