Theory of Computation: Automata, and Regular Expressions

Theory of Computation

Automata Theory

Automata theory is a theoretical branch of computer science and mathematics that deals with the logic of computation using simple machines called automata. The main goal of automata theory is to develop methods for describing and analyzing the dynamic behavior of discrete systems. Automata consist of states (represented by circles) and transitions (represented by arrows).

Finite Automata

A finite automaton is an abstract computing device and a mathematical model of a system with discrete input, output, states, and a set of transitions between states that occur on input symbols from an alphabet. Finite automata are the simplest machines for pattern recognition, used to characterize regular languages, analyze and recognize natural language expressions, and model digital computers. They read an input string and change their internal state based on the current input symbol. Every automaton defines a language, which is the set of strings it accepts.

Applications of Automata Theory

• Compiler design
• Switching theory and the design and analysis of digital circuits
• Design and analysis of complex software and hardware systems
• Proving program correctness
• Designing finite state machines (e.g., Moore and Mealy machines)

Types of Finite Automata

Deterministic Finite Automata (DFA)

DFA stands for deterministic finite automata. "Deterministic" refers to the uniqueness of the computation. A DFA reads an input string one symbol at a time. There is only one path for a specific input from the current state to the next state. DFAs do not accept null moves (i.e., they cannot change state without an input character). A DFA can have multiple final states and is used in lexical analysis in compilers. The transition function is defined as: δ: Q x Σ → Q

Non-deterministic Finite Automata (NFA)

NFA stands for non-deterministic finite automata. NFAs are easier to construct than DFAs for a given regular language. An NFA can have multiple paths for a specific input from the current state to the next state. Not every NFA is a DFA, but every NFA can be converted into a DFA. NFAs differ from DFAs in two ways: they can have multiple next states for a given input, and they can have ε-transitions (transitions without any input symbol). The transition function is defined as: δ: Q x Σ → 2^Q

Regular Expressions

Regular expressions are a simple and effective way to describe the languages accepted by finite automata. Languages accepted by regular expressions are called regular languages. A regular expression is a sequence of patterns that defines a string. They are used to match character combinations in strings, and string searching algorithms use these patterns for string operations.

For instance:

• x* means zero or more occurrences of x: {ε, x, xx, xxx, xxxx, ...}
• x+ means one or more occurrences of x: {x, xx, xxx, xxxx, ...}

Pumping Lemma

Theorem:

For any regular language L, there exists an integer P (the pumping length), such that for all w in L with |w| ≥ P, we can break w into three strings, w = xyz, such that:

1. |xy| ≤ P
2. |y| > 0
3. For all k ≥ 0, the string xy^kz is also in L.

Steps to prove a language is not regular using the Pumping Lemma:

1. Assume L is regular.
2. The pumping lemma should hold for L.
3. L has a pumping length P.
4. All strings longer than P can be pumped (|w| ≥ P).
5. Find a string w in L such that |w| ≥ P.
6. Divide w into xyz.
7. Show that xyⁱz ∉ L for some i.
8. Consider all ways w can be divided into xyz.
9. Show that none of these divisions satisfy all three pumping conditions simultaneously.
10. If w cannot be pumped, this leads to a contradiction, proving L is not regular.