Introduction to the theory of computation (Sipser)

Michael Sipser

18 flashcards · Mathematics · by lakesare

Build the finite automaton that recognizes this language: Alphabet is {0,1} and that the language consists of all strings with an odd number of 1s. Suppose that you are given some language and want to design a finite automaton that recognizes it. Pretending to be the automaton, you receive an input string and must determine whether it is a member of the language the automaton is supposed to recognize. You get to see the symbols in the string one by one. After each symbol, you must decide whethe…
Do you need to remember the entire string seen so far in order to determine whether the number of 1s is odd? Of course not. Simply remember whether the number of 1s seen so far is even or odd.
FORMAL DEFINITION OF COMPUTATION
machine starts in the start state. machine goes from state to state according to the transition function. machine accepts its input if it ends up in an accept state. We say that M recognizes language A if A = {w| M accepts w}.
What do NFA vs DFA stand for?
NFA - nondeterministic finite automaton DFA - deterministic finite automaton NFA (nondeterministic finite automaton, or nondeterministic finite-state automaton).
What's the difference between NFA (nondeterministic) and DFA (deterministic) finite automaton. Nondeterministic finite-state automatonHow does an NFA compute? Suppose that we are running an NFA on an input string and come to a state with multiple ways to proceed. For example, say that we are in state q1 in NFA N1 and that the next input symbol is a 1. After reading that symbol, the machine splits into multiple copies of itself and follows all the possibilities in parallel. Each copy of the mach…
1. NFA - a state may have zero, one, or many exiting arrows for each alphabet symbol. In the DFA every state has exactly one exiting transition arrow for each symbol in the alphabet. 2. In NFA, ε symbol is allowed. In a DFA, labels on the transition arrows are symbols from the alphabet. This NFA has an arrow with the label ε. In general, an NFA may have arrows labeled with members of the alphabet or ε. Zero, one, or many arrows may exit from each state with the label ε.
What would happen if we feed the word '010110' to this NFA? Nondeterministic finite-state automaton
On input 010110, start in the start state q1 and read the first symbol 0. From q1 there is only one place to go on a 0—namely, back to q1—so remain there. Next, read the second symbol 1. In q1 on a 1 there are two choices: either stay in q1 or move to q2. Nondeterministically, the machine splits in two to follow each choice. Keep track of the possibilities by placing a finger on each state where a machine could be. So you now have fingers on states q1 and q2. An ε arrow exits state q2 so the ma…
Here is the definition of the deterministic finite automaton. What's the definition of the nondeterministic finite automaton? DFA (deterministic finite automaton).
Only the transition function is different - in an NFA, δ(state, input symbol or ε) ➝ set of possible next states. NFA (nondeterministic finite automaton)Σε means Σ ∪ {ε}.P(Q) means all subsets of Q (a power set). Example:
How can this DFA be simplified?
We can remove the states {1} and {1,2}, because no input leads to them. We may simplify this machine by observing that no arrows point at states {1} and {1, 2}, so they may be removed without affecting the performance of the machine.
What does the {2,3} state signify in the DFA? DFA NFA
It means the state in the corresponding NFA where we keep our finger on state 2 and state 3. Suppose we had the input ba.In the NFA: after ba, we'd have to keep our finger on state 2 and state 3.In the DFA: after ba, we'd be in the state {2,3}.
How would we go about proving that if A1 and A2 are regular languages, then A1 ∪ A2 is a regular language. That is, that regular languages are closed under the union operator. Regular languages are closed under all three of the regular operations.
We know: there exist finite automaton M1 (for A1) and finite automaton M2 (for A2). A1 and A2 being regular languages means that there exist finite automatons that recognizes these languages.We want to prove: there exists some automaton that recognises A1 ∪ A2. A proof by constructing such A1 ∪ A2 automaton!
What 2 ways to prove that regular languages are closed under the union operator are there? Regular languages are closed under all three of the regular operations.
Using the deterministic finite automaton (harder) Using the nondeterministic finite automaton (easier) Construction of an NFA N to recognize A1 ∪ A2
Suppose you have 2 automatons that recognize languages A1 and A2. How would you build an automaton that recognises the language A1 ∪ A2? Construction of an NFA N to recognize A1 ∪ A2 Regular languages are closed under all three of the regular operations.
Suppose you have 2 automatons that recognize languages A1 and A2. How would you build an automaton that recognises the language A1 ◦ A2? Construction of an NFA N to recognize A1 ∪ A2 Regular languages are closed under all three of the regular operations.
Suppose you have 2 automatons that recognize languages A1 and A2. How would you build an automaton that recognises the language A*? Construction of an NFA N to recognize A* Regular languages are closed under all three of the regular operations.
What shortcuts are used here? The value of the arithmetic expression is the number 32. The value of a regular expression is a language.
The symbols 0 and 1 are shorthand for the sets {0} and {1}. So (0 ∪ 1) means ({0} ∪ {1}). The value of this part is the language {0,1}. The part 0* means {0}*, and its value is the language consisting of all strings containing any number of 0s. The concatenation symbol ◦ often is implicit in regular expressions. (like the × symbol in algebra) thus (0∪1)0* actually is shorthand for (0∪1) ◦ 0∗.
Many neat regexes Precedence of the operators: star, concatenation, union.
What does the pumping lemma claim?
That if L is a regular language → there exists a number p (pumping length) such that every string w in L of length at least p can be written as w = xyz satisfying these 3 conditions: (1) means the loop y to be pumped must be of length at least one;(2) means the loop must occur within the first p characters. (1) and (2) means that |x| must be smaller than p, but apart from that, there is no restriction on x and z.
What can the pumping lemma be used for? Pumping lemma
For proving that some language L is not a regular language. The pumping lemma is often used to prove that a particular language is non-regular: a (of the language's regularity) may consist of exhibiting a word (of the required length) in the language that lacks the property outlined in the pumping lemma. Finite languages vacuously satisfy the pumping lemma by having p equal to the maximum string length in L plus one.
How would you prove that language L is not regular? Pumping lemma
[Proof by contradiction] Suppose L IS regular, and show that there exists: a word in language L of length > p (some pumping length) that can NOT be written as xyz satisfying the 3 conditions. This would be a contradiction, because the Pumping lemma promises that if L is regular, then EVERY word of length >p would satisfy the 3 conditions.