I have to write the language of the below $NPDA$(Non-Deterministic Push Down Automata). enter image description here

I think that from $q_0$ to $q_1$ and then $q_2$, we are actually building the below all the strings of $0$'s and $1$'s of the form $a^nb^n$ with the lenght at least 2.

But there is also a transition from $q_2$ to $q_0$, which makes a cycle, and it just read a $1$ from input string. For example these strings are accepted by this machine, and the point is that in all of them the last character is $0$.

1100 1 10 1 1100

111000 1 1100 1 10


But, unfortunatly I don't know how to write its language accuratly. My idea was to write something like the below language:

$L = \{ w(1^n) z (0^n) | w ∈ L \}$ and $z ∊ \{1,ɛ \}$

But it is not correct. I will be grateful for any help.

  • $\begingroup$ Isn't a NPDA a non-deterministic pushdown (rather than finite) automaton? $\endgroup$
    – Nathaniel
    Commented Apr 30, 2022 at 16:47
  • $\begingroup$ Yes. You are right, sorry, it was a mistake.@Nathaniel $\endgroup$ Commented Apr 30, 2022 at 17:06

1 Answer 1


Consider $L = \{1^n0^n\mid n>0\}$. It seems that the language of your PDA is $L(1L)^*$.

It is not exactly the way you wanted, but I think it is an accurate and short way to write it.

You could be a bit more verbose and write it as:

$$\{1^{n_1}0^{n_1}11^{n_2}0^{n_2}1…11^{n_k}0^{n_k}\mid k \geqslant 1 \wedge \forall i\in \{1, …, k\}, n_i > 0\}$$

  • $\begingroup$ I think because of the cycle we should use recursion in our language. But are we allowed to use of $*$ sign in our set? $\endgroup$ Commented Apr 30, 2022 at 17:09
  • $\begingroup$ Actually, I wanted to work with an string such as $w$, because we have been told that we can not use of $*$ sign in our set🤔 $\endgroup$ Commented Apr 30, 2022 at 17:13
  • $\begingroup$ Not in the way you want, because if $u$ is a word, $u^*$ is a regular expression that is considered as a set, so something like $\{u^*\mid u \in L \}$ would be a set of sets of words. $\endgroup$
    – Nathaniel
    Commented Apr 30, 2022 at 17:14
  • $\begingroup$ @AylinNaebzadeh I edited the answer. $\endgroup$
    – Nathaniel
    Commented Apr 30, 2022 at 19:08
  • $\begingroup$ But I think each $1$ between $1^n0^n$ is not necessary. $\endgroup$ Commented May 1, 2022 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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