CS 420 2024fall ibarland

most recent semester

Organization of Programming Languages
ITEC420 archive

ITEC420 is an introduction to the study of computability and formal languages. Topics include:

• Languages and problems
• Basic proof techniques
• Automata and recognizers; Grammars and generators
• Parse Trees
• Finite-state machines / regular grammars / regular expressions
• Nondeterministic automata
• Pushdown Automata
• The Pumping Lemma for FSMs and PDAs
• Turing Machines
• The Halting Problem, and the Church-Turing Thesis

• Demonstrate an ability to understand and apply mathematical concepts.
• Describe, analyze, and design language generators and recognizers including context free grammars and both deterministic and non-deterministic finite automata, pushdown automata, and Turing machines.
• Use a Pumping Lemma to prove that a language is not in a given class.
• Explain the Church-Turing Thesis and its significance.
• Describe example unsolvable problems and outline how a problem can be shown to be unsolvable.
• Define the classes P, NP, NP-Complete and explain their significance.

Course pages, past and present

• 2024fall:      Barland
• 2023fall:      Barland
• 2022fall:      Barland
• 2021fall:      Barland
• 2020fall:      Barland
• 2019fall:      Okie For detailed information on previous semesters, contact Dr. Okie.

most recent semester

This page licensed CC-BY 4.0 Ian Barland Page last generated

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu