Finite Automata - Sipser 1.2 PDF

# 1. Finite Automata - The theory of computation begins with a question: what is a computer? - Real computers are quite complicated. - We can use an idealized computer called a **computational model**. - This model is accurate in some ways but not necessarily others. - We will use several model...

# 1. Finite Automata - The theory of computation begins with a question: what is a computer? - Real computers are quite complicated. - We can use an idealized computer called a **computational model**. - This model is accurate in some ways but not necessarily others. - We will use several models depending on the features we need to focus on. - We begin with the simplest model, called the **finite state machine** or **finite automaton**. ## 1.1. Finite Automata - Finite automata are good models for computers with an extremely limited amount of memory. - They are the heart of many electromechanical devices. - For example, the controller for an automatic door. - It has a pad in front to detect the presence of a person about to walk through the doorway. - It has a pad in the rear to hold the door open so that the person doesn't get hit. - It has two states **OPEN** or **CLOSED**. - **State diagram**: - It is a diagram that shows the possible states and transitions of an automation. - The controller is a computer with just one bit of memory. - It can be represented in four possible input conditions: - **FRONT** - **REAR** - **BOTH** - **NEITHER** - **Figure 1.2** shows the transition table for the automatic door controller. - The controller moves between states depending on the input it receives. - It's like a simple computer, but it has limited memory. - Other household appliances, such as dishwashers and thermostats can also be described with finite automata. - **Markov chains** are useful for recognizing patterns in data. - **Finite automata** are a mathematical concept that can be used to solve problems in computer science. ## 1.1 Formal Definition of a Finite Automaton - We need a definition of a finite automaton that is precise and has good notation. - A finite automaton is defined formally as a **5-tuple**: - A set of **states**, Q - A finite set of **input symbols** or **alphabet**, Σ - A **transition function**, δ: Q × Σ → Q - A **start state**, q0 ∈ Q - A set of **accept states**, F⊆Q - The **formal definition** of a finite automaton resolves ambiguities and clarifies the concept. ## 1.1. Examples of Finite Automata - **Figure 1.6** is a finite automaton with three states. - **Figure 1.8** is a finite automaton with two states. - **Figure 1.10** is a finite automaton with two states. - **Figure 1.12** is a finite automaton with five states. - **Figure 1.14** is a finite automaton with three states. - We can describe each finite automaton formally by giving its five parts. - The **language of a machine** is the set of strings accepted by that machine. ## 1.1. Designing Finite Automata - We can design a finite automaton using a variety of techniques. - One is to put yourself in the place of the machine and pretend to recognize the language. - This is done with a finite set of states, which represents the information that we need to remember. - Then the transitions are assigned based on how to go to that state based on the input. - We can describe this with a **state diagram**. # 1.2 Nondeterminism Non-determinism is an important concept in the theory of computation. - **deterministic finite automation (DFA)** has exactly one transition arrow for each symbol. - **nondeterministic finite automation (NFA)** has a choice of next state, and that is represented as multiple arrows coming out of the state with different labels. - It also can have **ε arrows** coming from one state to another that are not labeled. - In an NFA, when we are in a state with multiple exits, the machine "splits" into multiple copies of itself, and each copy takes a different path. - If any copy hits an accept state, then we say that the NFA accepts the input. - **Nondeterministic** means you can't say for certain which next state the machine will go to based on the current state and the current symbol. - **Deterministic** means you can always tell which next state the machine will go to based on the current state and the current symbol. - **Theorem 1.39** proves that every nondeterministic finite automaton has an equivalent deterministic finite automaton. - It shows a procedure for converting NFA's into DFA's so that they produce the same language. - Nondeterministic finite automata are easier to understand sometimes. # 1.3. Regular Expressions - In arithmetic, we can use operations such as addition and multiplication to construct expressions. - In the theory of computation, we can use the regular operations to build up expressions that describe languages. - **Regular expressions** are a shorthand notation for describing languages that are accepted by finite automata. - They are very useful for describing patterns in text. - **Figure 1.32** is the state diagram of a DFA for a language that is described by a regular expression. ## 1.3. Formal Definition of a Regular Expression - A regular expression is defined formally: - It is simply a symbol from the alphabet. - It is the empty string, ε. - It is the empty set, Ø. - It is the union of two regular expressions. - It is the concatenation of two regular expressions. - It is the star of a regular expression. - **Theorem 1.54** proves that a language is regular if and only if some regular expression describes it. - It shows how to convert every regular expression into a finite automaton, and vice versa. - The **star operation** is a unary operation that repeats the string. - **Precedence order**: - Star is done first. - Concatenation is done second. - Union is done last. # 1.4 Nonregular Languages - Some languages cannot be recognized by any finite automata, or DFA. - These languages are called **nonregular languages**. - **Pumping Lemma for Regular Languages**. This lemma states that if a language is regular, then every string in that language of length p or greater can be "pumped". ## 1.4. Proof of The Pumping Lemma - We assume that A is a regular language, and that a DFA, M, recognizes it. - The pumping length, p, is the number of states in the DFA. - We can use the **pigeonhole principle**. - It states that if there are more pigeons than pigeonholes, then at least one pigeonhole must contain two pigeons. - This means that in the sequence of states that the DFA goes through when processing the string s, at least one state must repeat. - This gives us a contradiction, proving that A is not regular. - For most of the proofs, it is necessary to find a string s that cannot be pumped. # 1.5 Equivalence with Finite Automata - Regular languages are also described by regular expressions, finite automata, and pushdown automata. - The equivalence between regular expressions and finite automata can be shown by converting one to the other. - **Theorem 1.39** shows how to convert any NFA into an equivalent DFA. # 2. Context-free Languages - Context-free languages are a more powerful type of language than regular languages. - They can describe more complex features, such as recursive structure. - **Context-free grammars** are a method for describing context-free languages. - They consist of a set of variables, terminals, and rules. - **Rules** are of the form A → w, where A is a variable and w is a string of variables and terminals. - The **language of a grammar** is the set of all strings that can be derived from the start variable. - **Parse trees** are a pictorial representation of a derivation. - **Figure 2.1** shows a parse tree for the string 000#111 in grammar G1. ## 2.1. Examples of Context-free Grammars - **Grammar G3** generates strings of properly nested parentheses. - **Grammar G4** generates arithmetic expressions. ## 2.1. Designing Context-free Grammars - It's not easy to design context-free grammars. - Here are some techniques: - **Breaking into simpler parts**: some context-free languages are the union of simpler context-free languages. - We can create separate grammars for the simpler parts and then combine them into one grammar. - **Constructing a DFA**: If a language can be recognized by a DFA, then we can convert the DFA into an equivalent context-free grammar. - **Identifying linked substrings**: If a language has substrings that need to be linked together, we can use a rule of the form R → uRv . - **Recursive structure**: If a language has a recursive structure, then we can place the variable that generates the structure in the appropriate place in the rules. ## 2.1. Ambiguity - A grammar is **ambiguous** if it generates the same string in more than one way. - The ambiguous string will have multiple parse trees. - **Figure 2.6** shows an ambiguous grammar. - Sometimes, we can find an unambiguous grammar that generates the same language. - For some languages, it is impossible to find an unambiguous grammar. - These languages are called **inherently ambiguous**. ## 2.1. Chomsky Normal Form - We can convert any context-free grammar into **Chomsky Normal Form**. - A grammar in Chomsky Normal Form has rules of the form A → BC or A → a. - It helps us simplify grammars and make them easier to work with. - **Theorem 2.9** states that any context-free language can be generated by a context-free grammar in Chomsky Normal Form. # 2.2. Pushdown Automata - A **pushdown automaton (PDA)** is a computational model that is similar to a finite automaton, but it has an additional component called a **stack**. - The stack is a “last in, first out” storage device. - It can be used to store an unlimited amount of information. - **Theorem 2.20** proves that pushdown automata and context-free grammars are equivalent in power. - This means that any language recognizable by a pushdown automaton is also context-free, and vice versa. - **Nondeterministic pushdown automata** are more powerful than deterministic pushdown automata. ## 2.2. Formal Definition of a Pushdown Automaton - A pushdown automaton is defined formally as a 6-tuple: - A set of **states**, Q - A finite set of **input symbols** or **alphabet**, Σ - A finite set of **stack symbols** or **stack alphabet**, Γ - A **transition function**, δ: Q × Σε × Γε → P(Q × Γ₂) - A **start state**, q0 ∈Q - A set of **accept states**, F⊆Q - The **transition function** takes the current state, the next input symbol, and the top symbol of the stack, and outputs a set of possible next states and stack operations. ## 2.2. Equivalence with Context-free Grammars ### Converting a CFG to a PDA - We can convert a CFG, G, into an equivalent PDA, P, that recognizes the same language. - We use **nondeterminism**: The PDA has to choose a rule to use at each step of the computation. - We use a **stack** to store part of the intermediate string of the derivation. --- We use a strategy to remember the part of the intermediate string starting from the first variable symbol. And we use an extra state 0 that is called "loop". Its job is to consume the terminal symbols in front of the first variable. - **Figure 2.24** shows the state diagram of the PDA. - The automaton makes transitions by reading the symbols from the input or popping the symbols from the stack. ### Converting a PDA to a CFG - **Lemma 2.21** proves that a language is context-free if some pushdown automaton recognizes it. - We convert any **finite automaton** (DFA) into an equivalent **GNFA** and then to a regular expression. Then we convert any **GNFA** into an equivalent regular expression. After we convert any **PDA** to an equivalent GNFA, we already proved that any GNFA can be converted into a regular expression, so we can convert a PDA to a regular expression. - The idea for converting a PDA, P, into an equivalent context-free grammar, G, is to design G to simulate P. - We use a variable Apq for each pair of states, p and q. - We use a rule of the form Apq→ aArsb if δ(p, α, ε) contains (r, t) and δ(s, b, t) contains (q, ε). - We use a rule of the form Apq → Apr Arg if δ(p, ε, ε) contains (r, ε). - We use a rule of the form App → ε. - **Figure 2.28 and 2.29** are diagrams that illustrate the PDA's computation for each of the rules. - **Lemma 2.27** proves that if a language is recognized by a pushdown automaton, then it's context free. # 2.3. Noncontext-free Languages - Some languages are not context free. - We can use the **Pumping Lemma for Context-free Languages** to prove that a language is not context free. - **Figure 2.35** illustrates the idea behind this lemma. ## 2.3 Proof of The Pumping Lemma - If A is a context-free language, then there is a pumping length, p. - Any string in A of length p or greater can be pumped. - **Figure 2.35** shows how to pump a string. We cut the string into five pieces and repeat the second and fourth pieces. - This lemma works because of the **pigeonhole principle**. - In a parse tree for a string that is long enough, at least one variable symbol will appear at least twice on some path from the root to a leaf of the parse tree. - We can use the repetition of that variable symbol to pump the string. # 2.4. Equivalence with Pushdown Automata - Pushdown automata and context-free grammars are equivalent in power, meaning that any language recognized by a context-free grammar is also recognizable by a pushdown automaton, and vice versa. This equivalence is useful because we can choose either a grammar or an automata recognizing the same language. - The **power of pushdown automata** is significant because they can recognize some languages that are not regular. # 2.5 Ambiguity - A grammar is **ambiguous** if it can produce the same string in multiple ways. - If a string has more than one parse tree, it has an ambiguous derivation. - **Figure 2.6** shows two parse trees for the string a+axa, proving that this grammar is ambiguous. - Some languages, like {a²bcki, j, k≥ 0 and i = j or i = k} are **inherently ambiguous**; for example, they can only be generated with ambiguous grammars. # 2.6 Chomsky Normal Form - A context-free grammar is in **Chomsky Normal Form** if all its rules are of the form A → BC or A → a. - A rule of the form S → ε is permitted, where S is the start variable. - **Theorem 2.9** states that every context-free language can be generated by a grammar in Chomsky Normal Form. # 2.7. Equivalence with Pushdown Automata - Pushdown automata and context-freelanguages are equivalent in power. - This means that we can convert any context-free grammar into a pushdown automaton. - **Figure 2.24** is the state diagram of a PDA. - This automaton accepts strings if it can derive a string from the start variable of the grammar. - **Lemma 2.27** proves that if a language is recognized by a pushdown automaton, then it's context free. - This is the reverse direction of Theorem 2.20. - **Theorem 2.20** proves that a language is context free if and only if some pushdown automaton recognizes it. - The proof for converting a PDA into a context-free language focuses on generating a variable Apq for each pair of states p and q and designing the rules of the grammar to generate strings. - **Figure 2.28 and 2.29** illustrate the computation of the PDA for each of the rules. - This theorem proves the equivalence of pushdown automata and context-free grammars. # 2.8. Noncontext-free Languages - **The Pumping Lemma for Context-free Languages** states that any sufficiently long string s in a context-free language can be pumped, meaning that it can be divided into five pieces, s= uvxyz, and the second and fourth parts can be repeated together any number of times, remaining in the language. - **Figure 2.35** illustrates the concept of pushing a string. - We can prove that a language is not context-free by finding a string s that cannot be pumped. - This is a proof by contradiction. - **Example 2.36** is an example of a language that is not context free and cannot be pumped, because it's based on the number of symbols, which would change after pumping.