The way to use JFLAP to do a Pushdown Automaton

Question

I need to create a Pushdown Automaton with JFLAP that recognizes the following language:

What steps need to be taken to do it? And how does it work?

Answer 1

I think that this question is better suited for cs.stackexchange.com but I'll add my solution anyway.

Forming an example

It's actually easier than it looks, let's consider for the sake of an example that we have the following values for our occurrences:

n = 2
m = 3
p = 1

This should allow us to form the following string:

a²b³c¹a¹⁺³b² = aabbbcaaaabb

Forming logical understanding

From this we need to determine which symbols we need to keep a track of.

1. We know that the outer symbols occur n times and that n,m ≥ 1 so we need to keep a track of n here and we require it to occur at least once.
2. We know that q = p+m and m also occurs at least so we need to keep a track of the occurrences of m.
3. If q = p+m we also need to keep an occurrence of p but note that p can also not occur because it is stated that p ≥ 0.

Forming a formal definition

We let our PDA P to be the following PDA:

P = (Q, Σ, Γ, τ, q₀, Z, q₆)

Where:

• Q is the set of states in our d-PDA
• Σ is the input symbol containing the string
• Γ is the stack symbol containing the set Γ = {a,b}
• q₀ is our initial (start) state
• Z is our stack symbol #
• q₆ is our final (end) state

Forming a pushdown automaton

So from this we can form the following automaton (in JFLAP):

So here, we are just keeping a track the symbols as mentioned above but an important thing to note here is q3 where the transition for c is a 0 or more transition.

We also use the symbol # as the stack symbol.

Simulation

If we simulate this PDA with the input as specified above (aabbbcaaaabb), we get the following results: