nlytridis / computation-theory

Course Work

Computational Theory

Course's Project Verbal and Syntactic Analysis of the *PTuc Programming Language

• flex
• bison

*(PTUC is a Pascal based language used in this course for educational purposes).

Course Description

Sets, relationships, alphabets, languages. Finite distinctions, formulations,languages. Equivalence of finite machines and technical distinctions. Automatic minimization. Verbal analysis. Automatically stack, grammatical differences, required services. Automatic stack equivalence and grammatical technical distinctions. Syntactic analysis. Turing machines and extensions for grammatical differences, retrospective languages. Non-determinism, non-deterministic Turing machines, retrospectively listed languages. Hierarchy of languages. From the same creators, they distributed, they did not solve. The participation of the churches and Turing. Universal Turing machines, reductions. Rice Theorem. Computational complexity and complexity classes. NP-complete and polynomial reductions. Cook's theorem. Treatment of NP-fullness. Application on request compilation and teaching labs sometimes flex, bison, JavaCC