| This course has the purposes: to understand the classes of formal grammars: the regural grammar, the context-free grammar, the context-sensitivy grammar, and the phrase structure grammar, and those of automatons: the finite-state automata, the pushdown automata, the linear-bounded automata, and the Turing machines. Also it aims at understanding the Chomsky hierarchy of them and the incomputability of the halt problem of the Turing machine. |
| Students should understand the concepts of grammar that generates formal languages and their families, regular grammar, context-free grammar, context-dependent grammar, and phrase structure grammar. In addition, students understand finite state automata, pushdown automaton, linearly constrained automaton, and Turing machine as mathematics of "machine" that accepts formal language. Furthermore, they understand Chomsky's hierarchy, which is the correspondence between grammar and machine through language families. As for the problem of stopping the Turing machine, they understand the structure of the proof and the assertion of the problem. |