Formal Language

Deterministic finite automata: Transition Diagrams, Language of an automation, Nondeterministic finite automata, Subset construction, ε-transitions, Application: text-searching.

Regular expressions: Regular expression in practice, Equivalence of regular expression and finite automata, The algebra of regular expression, Testing algebraic identities.

Properties of regular language: The pumping lemma, Boolean operations, Testing emptiness of regular languages, Testing membership in an regular languages, Testing Distinguishability of states, Minimizing DFA

Context-free grammars: Derivations and languages, Leftmost and rightmost derivations, Sentential forms, Parse trees, Equivalence of parse trees and derivations, Ambiguous grammars, Eliminating ambiguity, Parsers, Document type definitions.

Push-down automata: Pushdown automata, Moves of a PDA, Acceptance by DPA, Instantaneous Descriptions, PDA and grammars, Deterministic PDA, Acceptance by deterministic PDA, The languages accepted by DPDA's.

Properties of CFL: Elimininating useless symbols, Eliminating ε- and unit-productions, Chomsky normal form, The pumping lemma, Operations that preserve CFL, Testing emptiness of a CFL, Testing membership in a CFL.

Turing machine and decidable languages: The Turing machine, Acceptance by a Turing machine, Recursively enumerable languages, Instantaneous descriptions of a TM, Storage in the finite control, Multiple tracks, Multitape TM, Nondeterministic TM, Semi-infinite tape TM, Multistack machine, Counter machine, Simulating a TM by a real computer, Simulating a computer by a TM.

Undecidability: Recursive and recursively enumerable languages, Complements of recursive and RE languages, Decidability and undecidability, The language \(L_d\), The universal language, Rice's theorem, Post's correspondence problem, Undecidable CFL problems.

Intractable problems: The class P and NP, The P=NP questions, Polynomial-Time reductions, NP-complete problem, NP-Complete satisfiability problems, Other NP-Complete problem.

The goal of the written homework is to help you refine the fundamental skills, and better understand the theoretical underpinnings, that you will need in order to do well on the exams. Grading for these assignments is based on the correctness of your answer, and the presentation of your reasoning. You should strive for clarity and conciseness, while making sure to show each step of your reasoning. Categorical answers with no explanation will not even receive partial credit, but lucid explanations of your attempt to find the answer will.

Written homework will be handed in in PDF format via Gradescope, and should preferably be typeset in LaTeX.

Students are expected to complete each assignment on their own, and should be able to explain all of the work that they hand in. Copying code or proof material from other students, from online sources, or from prior instances of this course is not allowed. However, you are encouraged to discuss assignments with each other at a sufficiently high level to avoid the risk of duplicating implementation or proof. Examples of this would be discussing algorithms and properties referred to in the assignment, helping other students with questions, discussing a general proof technique, or referring to an online source with useful information. Similarly, you may consult online sources, tutorials, and generative AI programs. If you find specifically helpful material it is critical that you (a) do not copy the code or proof, but study it as a guide and then do your own work, and (b) cite the source with a suitable URL in your solution. If you have questions about whether something might be permissible, contact the course staff before you proceed.

You will have a total of 5 late days to use throughout the semester, but you may use at most 2 for any given assignment. Due to grade submission deadlines, you are not allowed to use late days on some specific assignment, which will be announced when the are released.