The FORTRAN language: 10 DO 100 I = 1,10 100 CONTINUE 10 DO 100 I = 1.10 In FORTRAN, variables beginning with a letter between I and N were integers. Other variables outside that range were "real" floating point. The point is look how far ahead the compiler has to read before it knows what the line is trying to do. An "alphabet" is a finite, non-empty set of characters. A "string" is a sequence of characters over an "alphabet". Language: set of finite strings. The set itself does not have to be finite, but all the strings in the language are. "Accepting" a language: a computer program "accepts" a language when, given a string as input, the program HALTS with a YES or NO indicating whether the string is a member of the language. Chomsky hierarchy: Type 3 language: Regular expression, regular language, can be accepted by a program using finite memory. Examples of languages that are type 3: "All base 10 numbers divisible by 7" Here's how you picture this: You have a finite machine. The user types in the characters one at a time. When each character is entered, the machine does some "processing." When you're done entering, the machine gives the answer. [Start with 0. When a character is entered, multiply the stored number by 10, add the new character, mod by 7. If the stored number is 0, when you're done, YES, else NO.] 98 0 *10 = 0; 0+9 = 9; 9 mod 7 = 2. 2*10 = 20; 20+8 = 28; 28%7=0. YES "All strings in which no character appears twice in a row." Type 2 languages: context-free languages. OVERSIMPLIFICATION: these are languages that can be accepted by a machine with finite memory PLUS a stack of no fixed size. Examples of type 2 languages that are not type 3: "Balanced parentheses" [If you see a (, put something on the stack. If you see a ), pop the stack. If you try to pop from an empty stack NO, if the stack is not empty, when you're done then NO, otherwise YES. "a^n b^n" (A bunch of a's followed by a bunch of b's, with the number of a's exactly equal to the number of b's.)" "palindromes" aaabbb aaaaabbbbb Type 1: Context sensitive languages: languages that can be accepted by machines with unlimited RAM. (or by Turing Machines). "wordword" (The set of all strings whose first half exactly match the second half) "a^n b^n c^n" (Although a^n b^n is type 2, you throw a c in there, and it is no longer type 2) Type 0: Unrestricted: There is not necessarily a program that HALTS giving YES or NO. There is a program that HALTS if the string is in the language, and DOES NOT HALT if the string is not. But you do have the RAM model or a Turing Machine to work with. "The Halting Problem" We can characterize languages or types of languages as GRAMMARS or as MACHINES. Type 3: regular grammar OR finite automata Type 2: context-free grammar OR pushdown automata Type 1: context-sensitive grammar OR Turing Machine that always halts Type 0: unrestricted grammar OR TM that may not halt.