# Determine the language of the NPDA

I have to write the language of the below $$NPDA$$(Non-Deterministic Push Down Automata). 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

1100

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.

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

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\}$$

• I think because of the cycle we should use recursion in our language. But are we allowed to use of $*$ sign in our set? Apr 30, 2022 at 17:09
• 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🤔 Apr 30, 2022 at 17:13
• 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. Apr 30, 2022 at 17:14
• But I think each $1$ between $1^n0^n$ is not necessary. May 1, 2022 at 5:28