\( \newcommand{\ket}[1]{\vert#1\rangle} \newcommand{\bra}[1]{\langle#1\vert} \newcommand{\bigket}[1]{\bigl\vert#1\bigr\rangle} \newcommand{\bigbra}[1]{\bigl\langle#1\bigr\vert} \newcommand{\class}[1]{\mathrm{#1}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\real}{\mathbb{R}} \newcommand{\complex}{\mathbb{C}} \newcommand{\ip}[2]{\left\langle#1, #2 \right\rangle} \newcommand{\Tr}{\mathop{\mathrm{Tr}}\nolimits} \newcommand{\tr}{\mathop{\mathrm{tr}}\nolimits} \newcommand{\abs}[1]{\left\lvert#1 \right\rvert} \newcommand{\norm}[1]{\left\lVert#1 \right\rVert} \newcommand{\X}{\mathcal{X}} \newcommand{\Y}{\mathcal{Y}} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \newcommand{\E}{\mathop{\mathbb{E}}} \newcommand{\dif}{\mathrm{d}} \newcommand{\eps}{\epsilon} \newcommand{\val}{\mathrm{val}} \newcommand{\vale}{\mathrm{val}^*} \newcommand{\sign}{\mathrm{sign}} \newcommand{\BB}{\mathrm{BB}} \renewcommand\P{\class{P}} \newcommand\NP{\class{NP}} \newcommand\NTIME{\class{NTIME}} \newcommand\NPC{\class{NP}\text{-complete}} \newcommand\THREESAT{3\text{-}\mathrm{SAT}} \newcommand\TWOSAT{2\text{-}\mathrm{SAT}} \newcommand\TWOUNSAT{2\text{-}\mathrm{UNSAT}} \newcommand\NAESAT{\mathrm{NAESAT}} \newcommand\SAT{\mathrm{SAT}} \newcommand{\tuple}[1]{\langle#1\rangle} \newcommand{\pair}[1]{\langle#1\rangle} \newcommand\VC{\mathrm{VERTEX\text{-}COVER}} \newcommand\MAXCUT{\mathrm{MAX\text{-}CUT}} \)

Formal Languages and Automata

Zhengfeng Ji

Lecture 1: Formal Languages and Automata

About This Course

Welcome

This is an incomplete set of notes prepared by Zhengfeng Ji for the course. Please do not distribute.

Formal languages and automata

Lecturer

Zhengfeng Ji

Office: 1-707, Ziqiang Technology Building

Email: jizhengfeng@tsinghua.edu.cn

Research areas: quantum computing and theory of computing.

  • Teaching assistants

    Huiping Lin (lhp22@mails.tsinghua.edu.cn)

    Shenghan Gao (sh-gao24@mails.tsinghua.edu.cn)

  • This is the fourth time I have taught this course at Tsinghua.

  • Your feedback is welcome

Computation and mathematics

  • Also known as Introduction to the ToC in some universities

  • Key observation

    Computation, Mathematics, Logic

    Computational problems, devices, and processes can be viewed as mathematical objects.

    One interesting connection between computation and mathematics, which is particularly important from the viewpoint of this course, is that mathematical proofs and computations performed by the models we will discuss throughout this course have a low-level similarity: they both involve symbolic manipulations according to fixed sets of rules. (Watrous lecture notes)

    We will study different types of recursions, Kleene star, context-free grammars, and Turing machines.

What you will learn in this subject

  1. Finite automata and regular expressions
  2. Pushdown automata and context-free grammars (CFG)
  3. Turing machines and computability, and basic complexity theory

  • More importantly, we hope that you will learn how to write definitions and proofs rigorously and improve your mathematical maturity.

  • I offer a follow-up course next semester called Introduction to Theoretical Computer Science, which covers lambda calculus, advanced computability, complexity theory, probabilistic computation, cryptography, and propositions as types.

    See lecture notes at http://itcs.finite-dimensional.space

Teaching and learning

  • We use chalk and a blackboard.

    The chalk-and-blackboard method is better for teaching and learning theoretical subjects.

    In How to Speak, Patrick Winston (MIT) argues that a blackboard is the right tool for speaking when the purpose is to inform.

  • Please be actively involved!

  • Reviewing after each class is highly recommended.

  • We will hand out notes after each class for you to review the material covered in class.

  • The subject could be challenging for many of you.

    It has a different style and a different set of requirements.

  • Pause and think about the problem or theorem by yourself before looking at the proof.

    Barak: Even a five-minute attempt to solve the problem by yourself will significantly improve your understanding of the topic.

Textbook

Introduction to Automata Theory, Languages, and Computation (3rd ed.), by John Hopcroft, Rajeev Motwani, and Jeffrey Ullman.

Hopcroft: In 1986, he received the Turing Award (jointly with Robert Tarjan) for fundamental achievements in the design and analysis of algorithms and data structures. He helped to build research centers at Shanghai Jiao Tong University and Peking University.

Motwani: He received the Gödel Prize for the PCP theorem and was the author of another excellent textbook, Randomized Algorithms. He was the youngest of the three, but unfortunately, he passed away in 2009.

Ullman: He received the Turing Award (2020) for his work on compilers and was an author of the Dragon Book, Compilers: Principles, Techniques, & Tools. He was the Ph.D. advisor of Sergey Brin, one of the co-founders of Google.

Homework

There will be about 12 assignments.

You are strongly encouraged to complete them on time.

Grading

Mid-term: 25%

Attendance & homework: 15%

Final exam: 60%

Q & A

  • Online: WeChat group, learn.tsinghua.edu.cn, and email

  • Office hours: 4–5 p.m. on Tuesday

Why Study This Subject

Classic material (mostly developed between the 1930s and the 1960s)

Finite automata

  • Simple examples of finite automata

    This simple model enables a deep understanding of its properties and the development of efficient algorithms for manipulating it.

    Example 1. Figure 1.1: Push a button to switch between on and off, starting from the off state.

    Example 2. Search for the word the.

  • Finite automata are a valuable model for many important kinds of hardware and software.

    • Specification, verification, and model checking of systems of finite states, circuits, and communication protocols
    • Lexical analyzers for compilers
    • Text search

  • When and how were finite automata discovered?

    [McCulloch and Pitts, A logical calculus of ideas immanent in nervous activity, 1943]

    [Kleene, Representation of events in nerve nets and finite automata, 1956]

    [Rabin and Scott, Finite automata and their decision problems, 1959]

  • Regular expressions

    \([A-Z][a-z]*\) matches Computer

Context-free grammars

  • Grammars are useful models when designing software that processes data with a recursive structure.

    Programming languages

    Compilers never enter an infinite loop.

  • Pushdown automata

    A machine with a single stack.

Turing machine

  • What can a computer do at all?

    Hilbert's 1928 Entscheidungsproblem (cf. Hilbert's tenth problem about Diophantine equations)

    The problem asks for an algorithm that takes a statement as input and answers Yes or No according to whether the statement is valid.

    What cannot be done on a computer?

    • We must know. We will know.

      The epitaph on his tombstone in Göttingen consists of the famous lines he spoke after his retirement address to the Society of German Scientists and Physicians on 8 September 1930.

  • What is computation?

    Church: Lambda calculus (\(\lambda x . x^2 + 2\))

    Gödel: Recursive functions

    Turing: Turing machines (age 24)

    You: C, Python, Java, …

  • The Turing machine is an intuitive model of computation, and Gödel was convinced by it.

    It's like waiting for the bus. We waited for 2000 years for a formal definition of computation; three buses come along at the same time.

  • They are all equivalent. Is mathematics invented or discovered?

  • Church-Turing thesis

  • Logic and computation

    Gödel's incompleteness: The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an effective procedure (i.e., an algorithm) is capable of proving all truths about the arithmetic of natural numbers.

  • What can a computer do efficiently?

    Space/time-bounded TMs

  • Extended Church-Turing thesis

Basics of FL&A

Sets and countability

Naive set theory treats the concept of a set as self-evident. This will not be problematic for this course, but it does lead to problems and paradoxes—such as Russell's paradox—when it is pushed to its limits.

Bertrand Russell and Russell's paradox. Let \(S\) be the set of all sets that are not elements of themselves: \(S = \{T : T \text{ is not in } T\}\). Is it the case that \(S\) is an element of itself? (Self-reference)

The size of a finite set \(S\) is denoted by \(\abs{S}\).

Sets can also be infinite.

Definition. A set \(A\) is countable if either (i) \(A\) is empty, or (ii) there exists an onto (or surjective) function of the form \(f : \mathbb{N} \rightarrow A\). If a set is not countable, we say that it is uncountable.

Power sets:

  • \(2^A\) or \(P(A)\)

  • More generally: What is \(A^B\)?

Theorem. The set \(\mathbb{Q}\) of rational numbers is countable.

Theorem (Cantor). The power set of the natural numbers, \(P(\mathbb{N})\), is uncountable.

There is a technique at work in this proof known as diagonalization. It is a fundamentally important technique in the theory of computation, and we will see instances of it later.

Central concepts of formal languages

  1. Alphabets

    An alphabet is a finite nonempty set of symbols.

    \(\Sigma = \{0,1\}\)

    \(\Sigma = \{a, b, c, \ldots, z\}\)

  2. Strings

    Strings are sequences of symbols chosen from an alphabet.

    0101 is a sequence over the alphabet \(\{0,1\}\).

    The empty string: \(\eps\)

    The length of a string: \(\abs{010} = 3\)

    Powers of an alphabet:

    \(\Sigma^3\)

    The set of all strings over an alphabet: \(\Sigma^*\)

    \(\Sigma^* = \cup_{n\ge 0} \Sigma^n\)

    \(\Sigma^+\)

    Concatenation \(xy\)

  3. Languages

    A language is a subset \(L\) of \(\Sigma^*\).

    Set-builder notation provides a way to define languages.

    For example, consider the set of binary numbers whose values are prime.

  4. Problems

    In automata theory, a problem is the question of deciding whether a given string is a member of some particular language.

  5. Union/concatenation/closure (star, Kleene closure)

    \(L \cup R\)

    \(LR\)

    \(L^* = \bigcup_{i=0}^\infty L^i\)

Proof techniques

  • Proofs about sets

    Ex. \(R \cup (S \cap T) = (R \cup S) \cap (R \cup T)\)

  • Proofs by contradiction

  • Proofs by induction

  1. Inductive proofs

    Prove a statement \(S(n)\) for every integer \(n \ge n_0\).

    Basis: \(S(n_0)\) is true.

    Induction: If \(S(n)\) is true, then \(S(n+1)\) is true for \(n \ge n_0\).

  2. Mutual induction

    Prove statements together!

    Example. In the on-off automaton,

    \(S_1(n)\): The automaton is in the off state after \(n\) button pushes if and only if \(n\) is even.

    \(S_2(n)\): The automaton is in the on state after \(n\) button pushes if and only if \(n\) is odd.

  3. Structural induction

    The most important proof technique for automata theory and programming languages.

    Ex. Trees

    Basis: A single node is a tree, and that node is the root of the tree.

    Induction: If \(T_1, T_2, \ldots, T_k\) are trees, then we can form a new tree as follows:

    1. Begin with a new node \(N\), which is the root of the new tree.
    2. Add copies of all the trees \(T_1, \ldots, T_k\).
    3. Add edges from node \(N\) to the roots of each of the trees \(T_1, \ldots, T_k\).

    Theorem. Every tree has one more node than it has edges.

    Proof. Use structural induction. Basis. The tree has a single node. Induction. Assume the claim is true for \(T_1, \ldots, T_k\), …

    Ex. Expressions

    Basis: Any number or letter is an expression.

    Induction: If \(E\) and \(F\) are expressions, then so are \(E + F\), \(E * F\), and \((E)\).

Reading

Lecture 2: Finite Automata

Outline

DFA, NFA, and \(\eps\)-NFA

An Informal Picture

Read Sec 2.1 of the textbook.

External actions drive the changes in the internal state.

What is a Finite Automaton

Examples

  • Finite automata are very simple models of computation that will be our focus for the next four to five weeks.

  • Computation with finite memory

  • Example 1. A finite automaton for the light switch.

  • Example 2. A finite automaton for accepting all binary strings that have length at least two and whose first two letters are different.

  • Example 3. A finite automaton for accepting all binary strings that are \(4 \pmod{7}\).

    0 1
    \(\rightarrow\) 0 0 1
    1 2 3
    2 4 5
    3 6 0
    \(*\) 4 1 2
    5 3 4
    6 5 6

  • We will talk about deterministic finite automata first.

  • Models we will not cover:

    Mealy machines (outputs determined by the input symbol and current state)

    Moore machines (outputs determined by the current state only)

Formal definition of DFA

Mathematical definition

  1. A finite set of states \(Q\)
  2. Input alphabet: A finite set of symbols \(\Sigma\)
  3. Transition function \(\delta : Q \times \Sigma \rightarrow Q\)
  4. A start state \(q_0 \in Q\)
  5. A set of final states \(F \subseteq Q\)

A deterministic finite automaton (DFA) is a five-tuple \(A = (Q, \Sigma, \delta, q_0, F)\)

Transition diagrams

See Examples 1 and 2.

They are best for visualization

Transition tables

Columns of state transitions

See Example 3 above.

They are machine friendly

How a DFA processes strings

  1. It starts in the start state.

  2. It enters a new state according to the transition function \(\delta\).

  3. It accepts if and only if the final state is accepting.

  • Examples

    Example. Design a DFA that accepts all and only the strings of 0's and 1's that have a \(01\) somewhere. That is, \(L = \{w \mid w = x01y \}\).

    The automaton needs to remember:

    1. Has it seen a \(01\)? If so, it accepts regardless of further input.
    2. Has it never seen a \(01\) but the most recent input is \(0\)?
    3. Has it never seen a \(0\)?

    This gives us a simple automaton with three states.

    Example. Design a DFA that accepts all and only the strings of 0's and 1's that have \(01\) as the last two letters. That is, \(L = \{w \mid w = x01 \}\).

    Note the differences at the accepting node.

    Example. Design a DFA that accepts all strings over \(\{0,1\}\) in which there is an odd number of occurrences of 01.

    For example, \(01000\) should be accepted while \(01001\) should not.

The language of a DFA

  • What do we mean by calling a language regular?

    A language is regular if it is the set of strings accepted by a finite automaton.

    Regular: arranged in or constituting a constant or definite pattern, especially with the same space between individual instances.

  • Succinct and precise, and leaves no ambiguities

Extended transition function

  • How to define \(\hat{\delta}(q, w)\) for a string \(w\)?

    Write \(w = xa\) and inductively define \(\hat{\delta}\).

    We can write the language of the DFA using the extended transition function: \(L(A) = \bigl\{w \mid \hat{\delta}(q_0, w) \in F\bigr\}\).

Are regular languages countable or not?

  • Yes!

  • This means that there are languages \(L \subseteq {\{0,1\}}^*\) that are not regular.

Nondeterministic Finite Automata

Nondeterminism

The machine can make guesses (non-deterministic choices) during computation.

Example

  • Binary strings whose 3rd letter from the end is a \(1\).

  • Example 2 with NFA:

Dead states and DFAs missing some transitions

They are not DFAs by definition, but they are in fact NFAs.

See Example 2.

Formal definition

It is still a five-tuple, but now the transition function is different. (The only difference)

Nondeterminism is reflected in the fact that \(\delta(q, a)\) is a set of states representing all possible target states when the current state is \(q\), and the input symbol is \(a\).

Extended transition function

  • Write \(w=xa\) and take the union of \(\delta(p_i, a)\) for all \(p_i \in \hat{\delta}(p_0, x)\).

The language of an NFA

  • Intuition and formal definition: \[\begin{equation*} L(A) = \bigl\{w \mid \hat{\delta}(q_0, w) \cap F \ne \emptyset \bigr\}. \end{equation*}\]

    The string is in the language as long as there exists a nondeterministic choice of path leading to acceptance.

DFA and NFA Equivalence

What does it mean?

Any language \(L\) has a DFA if and only if it has an NFA.

The direction from DFA to NFA is easy as any DFA is a special NFA.

NFA to DFA: idea

Subset Construction

  • The transition in an NFA is to a set of states (representing the nondeterministic choices).

  • Can we use a set of states (of the NFA) as the state of a DFA?

  • Transition: Union of target states for each state in the set.

NFA to DFA: proof

Let \(N\) be an NFA. We design a DFA \(D\) such that \(L(D) = L(N)\).

The five components of \(D\) are:

  1. The set of states \(Q_D\) is the power set \(2^{Q_N}\).

  2. The alphabet is the same \(\Sigma\).

  3. The transition rule \(\delta_D\) is

    \[\begin{equation*} \delta_D(S, a) = \bigcup_{q\in S} \delta_N(q, a). \end{equation*}\]

  4. Start state \(\{q_0\}\).

  5. Final states: any set that has nontrivial overlap with \(F\).

Now we need to show that the construction works, that is, \(w \in L(N)\) if and only if \(w \in L(D)\).

\(w \in L(N)\) means \(\delta_N(q_0, w)\) contains states in \(F\) and \(w \in L(D)\) means \(\delta_D(\{q_0\}, w)\) contains states in \(F\).

Induction on the length \(\abs{w}\) and prove that \(\delta_N(q_0, w) = \delta_D(\{q_0\}, w)\).

See Theorem 2.11 of the textbook.

Comments

DFA simulation of an NFA could have an exponentially large number of states.

Example: all bit strings whose \(n\)-th symbol from the end is \(1\).

Show that any DFA accepting those strings will have at least \(2^n\) states. (Pigeonhole principle)

Yet there is an NFA with \(n+1\) states for this. (The NFA first loops for a while on \(0,1\) and then moves \(n\) steps sequentially).