1
$\begingroup$

In computability we have the hierarchy of grammars "https://en.wikipedia.org/wiki/Chomsky_hierarchy". In this hierarchy we have many classes of grammar. This hierarchy has Turing machines at the top, and weaker machines lower. Machines are able to "recognize" languages within their class, and they are able to "decide" the halt-ability of weaker languages. "http://www.radford.edu/~nokie/classes/420/Chap3-Langs.html". Doing such tasks has different complexity classes based on the class of what is being acted on.

Here is my question: What is the process of determining the minimal class of machine required to recognize, and then decide, on a language. Also what is the cost of this function in relation to the class of machine?

I know that one way is to construct a grammar for a weak machine, see if it accepts, and then if you cant find one work your way up the hierarchy.

I certainly hope there is a solution to this problem besides just brute forcing potentially forever? Thanks!

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you ask for an (existence of) algorithm that can take your grammar and compress it to a lower type grammar? $\endgroup$
    – Valentin Tihomirov
    Jan 10, 2016 at 12:05
  • $\begingroup$ @ValentinTihomirov That is not the question I am asking. I assume that is impossible. I am asking for an (or the existence of) algorithm to determine the class of a machine required to run a program (besides brute force potentially forever). $\endgroup$
    – 44701
    Jan 10, 2016 at 12:13
  • $\begingroup$ So, you have just finished reading the table, which maps Unrestricted grammar => Turing Machine, Context-sensitive grammar => Linear-bounded automaton => Context-free grammar => Pushdown automaton and Regular grammar => Finite state automaton and ask for an algorithm to implement this simple 4-row tabe? It looks like a research-level question. $\endgroup$
    – Valentin Tihomirov
    Jan 10, 2016 at 13:06

1 Answer 1

Reset to default
2
$\begingroup$

Determining whether a context-free grammar generates a regular language is undecidable (this is exercise 9.107 in Singh's Elements of computation theory; the reduction is from the Post correspondence problem). So if you are OK with a language being given to you as a context-free grammar, then even determining whether a language is regular or context-free but not regular is undecidable.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks this helps a lot (clears up many things) but is there some algorithm to determine at least one category a language fits in (with other potential gray areas)? $\endgroup$
    – 44701
    Jan 10, 2016 at 13:06
  • 1
    $\begingroup$ There are many such algorithms, and I'm sure you can come up with some of them yourself. But the general problem cannot be solved algorithmically. $\endgroup$
    – Yuval Filmus
    Jan 10, 2016 at 13:07
  • $\begingroup$ @HarpoRoeder I wonder why determining if I can reduce CF => Regex is now what you ask but the algorhim able to determine if I can reduce CF => Regexp is what you are looking for? $\endgroup$
    – Valentin Tihomirov
    Jan 10, 2016 at 13:10

Your Answer

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

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