1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – ttnick Jun 15 '18 at 9:24
  • 1
    $\begingroup$ 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. :) $\endgroup$ – Seankala Jun 15 '18 at 11:25
2
$\begingroup$

I figured out the answer and hope this will help anyone with similar confusion in the future.

Since a pushdown automaton is essentially a finite automaton with an extra component called the stack which is used for storage, if we are presented with a regular language like the one given above, we simply need to create a PDA that does not use the stack. This concept confused me at first, but here's what I mean:

$$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.

Anyway, I hope this answer helps anyone else.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.