2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ 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). $\endgroup$
    – Raphael
    Commented Aug 2, 2015 at 17:26
  • $\begingroup$ 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. $\endgroup$
    – Evil
    Commented Aug 2, 2015 at 17:41
  • $\begingroup$ 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? $\endgroup$
    – Evil
    Commented Aug 2, 2015 at 17:55
  • 2
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Aug 2, 2015 at 18:52

1 Answer 1

Reset to default
3
$\begingroup$

No, a finite set of languages does not (usually) characterise infinite classes of languages. So any such specific tests are probably easy to fool.

For CFL in particular, there the Chomsky-Schützenberger characterisation. So if your model can deal with finitely many types of nested parentheses, it's probably at least as powerful as NPDA.

The generic proof technique for showing that one model is more powerful than another is simulation. You can find some examples via and, of course, in the literature.

Proof of the opposite is usually done by counter-example, i.e. a language that can be expressed in one but not the other model.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. Answer is more than I expected. And for given test, well I assumed that some kind of test showing for example recursion would be good, but I had nothing to support this conjecture. $\endgroup$
    – Evil
    Commented Aug 2, 2015 at 19:04

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.