# Chomsky hierarchy type determined by language

I have some modified automata and the task is to give the type of Chomsky hierarchy to it. All task is between type 3 and 0 noninclusive. For regular languages there are lot of tools and I can check it without problems, Turing Machine equivalent is also easy task, and there will be no such examples.

Now the question: is it sufficient to show that automaton can accept specified language of given type? From what I checked it would be sufficient to show equivalence to for example to NPDA, so I assume that if machine handles language that at least NPDA accepts it would be sufficient.

For example if machine can accept $a^nb^n$, it is type 2. If machine can accept $a^nb^nc^nd^n$ it is type 1? If not are there better examples of such languages or what steps should I follow?

• I'm not sure I understand your question. Note that there's always the possibility that the given model is not equivalent to any Chomsky class. It may fall between two of them, or be incomparable to some (or all). – Raphael Aug 2 '15 at 17:26
• I am interested in full capability. If something is able to handle type 2 and not full type 1, but is more powerfull than type 2, it is perfectly enough to tag it type 2 and do not investigate any further. I know there are types in between - it is not important. Question is about such test - is my assumption valid? If it is not, I do not know how to tackle this problem. – Evil Aug 2 '15 at 17:41
• For example CFL $L = \{\omega\omega^r, \omega \in \{a, b, c\}^+ \}$ so I would check if machine can accept it, if it does is it able to handle CFL? If not what should I check apart of this? – Evil Aug 2 '15 at 17:55
• No, of course not; why would any finite test bank characterise CFL? That said, it so happens that there is a neat characterisation for CFL; see here. – Raphael Aug 2 '15 at 18:52