# Nondeterministic PDA for the following language with Kleene star

I had a question regarding converting a language with the Kleene star production into a PDA. Here's the particular language I was looking at in my textbook:

$$L = (aaa^*bab)$$

My normal approach to constructing PDA's for languages would be to determine the pattern or rule of the language, and think to myself that it's sort of like counting the number of symbols using a stack, and determining whether the stack is empty at the end of the computation.

However, I'm not sure how to construct a PDA for languages like the one above where there isn't a particular rule regarding the $a^*$ production.

How would one normally handle these types of situations? Thank you.

• Since this language is regular (as it is given via a regular expression) you can construct a finite automaton from it (see e.g. Thompson construction). You do not need a PDA for this language, you can view the finite automaton as as PDA that does not use the stack at all, though. – ttnick Jun 15 '18 at 9:24
• Yes, I am aware that it's regular and can be expressed using a finite automaton. I was just wondering how to express regular languages using PDA's. Your comment regarding not using stacks gave me the right hint though, so thank you. :) – Seankala Jun 15 '18 at 11:25

$$L = (aaa^*bab)$$
$\space$
$$M = (Q, \Sigma, \Gamma, \delta, q_0, z, F)$$ $$Q = \{q_0,\ q_1,\ q_2,\ q_3,\ q_4,\ q_5\}$$ $$\Sigma = \{a,\ b\}$$ $$\Gamma = \{\}$$ $$z = \$$$$$F = \{q_5\}$$$\space$$$\delta(q_0, a, ) = \{(q_1,\ )\}$$ $$\delta(q_1, a, ) = \{(q_2,\ )\}$$ $$\delta(q_2, a, ) = \{(q_2,\ )\}$$ $$\delta(q_2, b, ) = \{(q_3,\ )\}$$ $$\delta(q_3, a, ) = \{(q_4,\ )\}$$ $$\delta(q_4, b, ) = \{(q_5,\ )\}$$$\space$I'm not completely certain about the stack start symbol, because I've noticed some resources use it regardless, while others assume that at the beginning the stack is empty ($\lambda\$) and push the start symbol at the first step.