How should Chomsky's Hierarchy and Turing Machines influence language design?

Question

I'm currently studying for a discrete mathematics test in which we are learning Chomsky's hierarchy and the type of automatas that recognize each level of the hierarchy. I'm being taught that most computer languages fall within "level 2 and 1" of the hierarchy, but not precisely how.

My questions are:

1. What features belong to each level?

2. Is this nothing more than theoretical basis? I'm wondering if language designers like Dennis Ritchie and James Gosling had to go into this considerations when designing C and Java. Do they? How would someone apply this?

3. We are being told that Turing Machines recognize the level 0 of the hierarchy. If so, are there any language features that belong to level 0? I'm guessing that this may be natural language processing, is it?

Answer 1

1. None. Level 1 includes Level 2. Maybe I misunderstood you, so to be complete:

   • Regular Languages are used within Regular Expression Matching. Colloquial: DFAs can not count. And you need to count if you want to match brackets. [Level 3]
   • Language Syntax is normally a Context Free Language. See 2) [Level 2]
   • Context Sensitive Language are used only theoretically. See 3) [Level 1]

2. It helps in designing lexers and parsers. I do not know if the creators of C thought about that, but Java, certainly. Parser Generator

3. Turing Machines calculate anything that can be calculated. "Can be calculated" is even defined as: Can be accepted by a Turing Machine. This includes, of course, natural language processing. Anything above Level 2 is not very useful for language generation, because a program reading such inputs may not stop (Word Problem can no longer be solved).

Answer 2

Type 3 grammars generate regular languages. These are languages with features like begins with "xxx", contains "xxx", ends with "xxx", contains an odd number of y's, etc. Finite automata (deterministic or non) recognize these languages.

Type 2 grammars generate context-free languages. These are languages with features like some number of x's followed by fewer, or more, or equal number of y's, or where a word is followed by the same word, but reversed. Pushdown automata recognize these languages...think Finite automaton with a stack.

Type 1 grammars generate context-sensitive languages. These are so close to Type 0 grammars that it is often hard to find a difference between them. LBAs (linear bounded automatons) recognize these languages, think Turing machine with limited resources...think a modern computer.

Type 0 grammars generate Turing languages, sometimes called recursively enumerable languages. These are basically any language that you could write a computer program to recognize, but they really blend with Type 1, since real computers generally have some kind of memory limit.

Finite automata, and pushdown automata are very important in solving problems that arise when writing compilers. However, that isn't why you study them, you study them to learn the limits of what can/cannot be computed. Many programmers think you can solve any problem with a computer. Computability theory teaches you otherwise.

Edit by "Dude" - OK, here is an easy to understand (and famous) problem that cannot be solved by any Turing machine or computer or programmer or alien genius...

Imagine you have some dominoes...but instead of patterns of dots, you have some short word on the top and bottom, say words like "aba" and "cab". If I give you 5 or 10 or 50 of these dominoes, can you arrange them so that the words on top, all concatenated together, match exactly the concatenated words on the bottom. You can make as many copies as you like of each and any domino.

Example dominoes (contrived :) (a/aab), (aba/ac), (cab/ab) is a set of 3 dominoes where the tops (a+aba+cab) exactly equals the bottoms (aab+ac+ab).

As easy as this might sound, it cannot be solved in general.

BTW, when I first read/understood this problem...I was thinking....ooooh, n! is starting to look good!