Cheap and Secure Web Hosting Provider : See Now

Minimal class of grammar required to run program

, , No Comments
Problem Detail: 

In computability we have the hierarchy of grammars "". 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. "". 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!

Asked By : Harpo Roeder
Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback