Automata and Formal Languages (Emre Sermutlu)

"Automata, Formal Languages and Turing Machines" - an excellent automata book by Emre Sermutlu. TODO: I should return to Chomsky Normal Form, and to the pumping lemmas, and to the Halting Problem chapter.

130 flashcards · Mathematics · by lakesare

What's plural for automaton?
Automata.
[Deterministic Finite Automaton] Why are some finite automata called deterministic?
Because their output can be determined in a unique way (from state, and from input).
[Deterministic Finite Automaton] DFA is formally a 5−tuple (Q, Σ, δ, q0, F). What does each symbol mean?
[Deterministic Finite Automaton] What language does the following automaton recognize? If A is the set of all strings that automaton M accepts, we say that A is the language of automaton M and write L(M) = A. This means M recognizes A.
All strings containing an even number of 1s. 0s do not make any difference, they do not change the state of the DFA. So this is all about 1s.This DFA accepts all strings containing an even number of 1s.
[Nondeterministic Finite Automaton] Nondeterminism is a kind of parallel computation.For the following NFA - when does a machine branch die?
machine branches - transition function returns multiple states, e.g. δ(q1, 1) = { q1, q2 }. They have the same structure but one is in state q1 and the other is in state q2. The same thing may happen again.machine dies - transition function returns 0 states, e.g. δ(q3, 0 or 1) = {}. We do not have to follow that machine any further.
Why is the notation 2S sometimes used for the power set P(S)? Power set is the set of all subsets of S (including {} and S itself).
Because the number of elements in P(S) is 2|S|. If S is a finite set with |S| = n elements, then the number of subsets of S is |P(S)| = 2n, which is the motivation for the notation 2S.
[Nondeterministic Finite Automaton] What do these mean in the definition of the NFA: Σε 2Q
Σε - alphabet AND the empty string ε: Σ ∪ {ε}. 2Q - the power set of all states: P(Q). This is the same definition as DFA except for the δ function. It takes ε as input in addition to symbols of Σ and gives a set of states as output.
[Nondeterministic Finite Automaton] What's the transition function δ of this NFA?
We omitted ε transitions because they are all empty set (because there are no ε transitions in this automaton!).
[Nondeterministic Finite Automaton] Verbally describe the language recognized by this NFA.
First, we have an any number of a's. (Possibly zero) Then we have an even number of b's. (Possibly zero) Then we have one or more c's.
[Nondeterministic Finite Automaton] Verbally describe the language recognized by this NFA.
[NFA - DFA equivalence] If NFA contains { q1, q2 } - what states does the equivalent DFA contain?
{ ∅, q1, q2, q12 }
[NFA - DFA equivalence] How to eliminate ε-transitions from the NFA?
Supersede all states with their ε-closures. ε-closures of a state is all states that can be reached by following ε-transitions from that state. Consider all states that can be reached from a state through ε-transitions, and call it the ε-closure of that state.Given: q1 → q4, q1 → q7The ε-closure of q1: q147Given: q1 → q4, q4 → q7The ε-closure of q1: q147Then, the start state of the new machine should be the ε-closure of the start state of the old machine.
[NFA - DFA equivalence] How many states will there be in the equivalent DFA? (together with the states unreachable from q1) Nondeterministic Finite Automaton
23 = 8
[NFA - DFA equivalence] What's δ(q12, a) in the equivalent DFA? Nondeterministic Finite Automaton
δ(q12, a) = q23 δ(q12, a) means 'a union of all states δ(q1, a) and δ(q2, a) result in'.q23 means { q2, q3 } (from the NFA).
[NFA - DFA equivalence] What's δ(∅, a) in the equivalent DFA? Nondeterministic Finite Automaton
δ(∅, a) = ∅ δ(q12, a) means 'a union of all states δ(q1, a) and δ(q2, a) result in'.q23 means { q2, q3 } (from the NFA).
[NFA - DFA equivalence] Here is a DFA we created from a NFA by creating 23 states, and following each δ(state, letter). How to make it smaller? Nondeterministic Finite Automaton
By eliminating the states unreachable from the start state .
[Union operator] What's the NFA recognising A ∪ B? DFAs recognizing A and B.
[Concatenation operator] Find the NFA recognizing A ◦ B: NFAs recognising A and B.
Check that this machine recognizes the language: {aaac, aabc, bbac, bbbc}
[Star operator] What's the NFA recognising A*? NFA recognizing A.
[Regular expressions] What's the operator precedence in regular expressions (concatenation, union, star)?
star concatenation union
[Regular expressions] What are union, concatenation & star operations defined on?
On sets. These are the same:Although a string and a set of strings are different concepts, we will use the same notation, because we will think of regular expressions as shorthand notations expressing languages. A regular expression, often called a pattern, specifies a set of strings required for a particular purpose. A simple way to specify a finite set of strings is to list its elements or members. However, there are often more concise ways: for example, the set containing the three strings "…
[Regular expressions] What's meant by 1. ∅ and 2. ε in the formal definition of regular expressions?
∅ = {} ε = { ε }
[Regular expressions] How would you build an NFA recognising this language? Language described by this regular expression.
Union means parallel, and concatenation means serial connections.
[Regular expression - regular language equivalence] A language is regular if and only if some regular expression describes it.How would you approach proving that if some regular expression describes a language then this language regular?
By building an NFA (from the regular expression). This is a proof by construction. Given the regex: We find the NFA:
[Regular expression - regular language equivalence] A language is regular if and only if some regular expression describes it.How would you approach proving that if the language is regular then there exists a regular expression that describes it. We will eliminate all intermediate states one by one until we obtain a 2−state machine. The label on the last remaining arrow will give us the regular expression we are looking for. Here, the rule is that the language of the machine must stay the same…
By building a regular expression (from the NFA). This is a proof by construction. Given the NFA: We find the regex:
[NFA] How would you simplify this NFA?
By superseding all states with their ε-closures.
[Regular expression - regular language equivalence] How would you find the regex equivalent to this NFA?
[Pumping lemma] What's the basic reason behind A = { 0n1n | n ≥ 0 } not being a regular language?
FSA needs infinitely many states to keep the number of symbols in memory. But it has finitely many states by definition.
[Pumping lemma] What's the intuition behind the pumping lemma?
If an NFA accepts a long string (≥ the number of states in the NFA), it MUST loop somewhere during the computation. If it turns around a loop once, it can turn around the same loop twice, three times, or any other number of times. It can also do zero turns. This operation of copying a part of a string and pasting it n times is called pumping. In a nutshell, pumping lemma says any sufficiently long string of a regular language can be pumped. An accepted string of length 4, abca. An accepted stri…
[Pumping lemma] What does it mean that 'pumping lemma says any sufficiently long string of a regular language can be pumped'? Use this example: An accepted string of length 6, abccca.
In our example, we can claim that any string of the form abc(cc)na should still belong to this language. Note that n ≥ 0. If it turns around a loop once, it can turn around the same loop twice, three times, or any other number of times. It can also do zero turns.
[Pumping lemma] What's the proof of the pumping lemma?
xy part of the string already contains a repetition. Since we know that y >= 1, |xy| is smaller than p (p is the number of states!)
[Pumping lemma] What's the contrapositive of:
[Context-free grammar] What are variables (V) and terminals (Σ) in this context-free grammar?
(variables) V = { S, A } (terminals) Σ = { 0, 1 }
When is a language regular VS context-free?
language is regular - iff there exists a DFA that recognizes it L = { w | M accepts w }. language is context-free - iff there exists a context-free grammar G with L = L(G)
What's the relationship between regular languages and context-free languages?
Every regular language is context-free.
[Context-free grammar] What does this language denote?
A set of all palindromes! abba, aa, abaaaba, bbbabbb are some palindromes.wR is a reverse of a string.
[Context-free grammar] How would you prove that this grammar generates all palindromes? Context-free grammar. Language consisting of all palindromes.
1. Show that if w is a palindrome, then w ∈ L. 2. Show that if w ∈ L, then w is a palindrome.
[Context-free grammar] What language this CFG generates?
A language of open & close parentheses.
[Context-free grammar] Find the parse tree for the derivation of the string 0011 using the grammar: One of the derivations:S→ AB→ 00AB→ 00B→ 001B→ 0011B→ 0011
[Context-free grammar] What's leftmost VS rightmost derivation of the string (e.g. 0011)? Context-free grammar
Leftmost derivation - at every step the leftmost remaining variable is replaced. Rightmost derivation - at every step the rightmost remaining variable is replaced. Leftmost and rightmost derivations have exactly the same parse trees. In other words, there is not a fundamental difference between these two derivations.
[Context-free grammar] When is the CFG said to be ambiguous?
Leftmost and rightmost derivations have exactly the same parse trees. In other words, there is not a fundamental difference between these two derivations.
[Context-free grammar] Why is this grammar ambiguous (based on the string a*b+c e.g.)?
Because it can generate a * b + c in 2 different ways:
[Context-free grammar] How does the notation L(G) reads?
Language L of the grammar G.
[Context-free grammars] Yields VS derives?
xBy yields xwy if there is a direct rule B → w in the CFG w derives x if if there is we can eventually get to x.
[Context-free grammar] Name 3 types of useless productions.
Dangling productions: A is non-reachable - if we can never derive A from S. Loopy productions: A is non-generating - we'll never derive a string of terminals. A's intermediates are non-generating - all intermediate steps to A contain non-generating variables.
[Context-free grammar] What are 2 rules to eliminate all useless productions?
[Context-free grammar] What's a unit production?
Production rule A → B where both A and B are variables.
[Context-free grammar] What's an ε−production?
Production rule A → ε.
[Context-free grammar] Why do we prefer to not have ε−productions in a grammar?
Because they make the analysis of the length of intermediate strings difficult. without ε−productions: on each step, length either increases or stays the same. with ε−productions: on each step, length may reduce (or increase, or stay the same).
[Context-free grammar] When is a variable A called nullable?
When it CAN eventually derive ε.
[Context-free grammar] How would you eliminate ε−productions from this grammar? Context-free grammar
Remove |ε Wherever the nullable variable was used on RHS, supersede 1A1 with 11. To eliminate ε−productions, we modify all the right-hand sides having nullable variables as follows: For each occurrence of a variable, add a rule (or rules) without it.
[Context-free grammar] How would you eliminate ε−productions from this grammar? Context-free grammar
Remove |ε Wherever the nullable variable was used on RHS, supersede 1A1 with 11. To eliminate ε−productions, we modify all the right-hand sides having nullable variables as follows: For each occurrence of a variable, add a rule (or rules) without it.
[Context-free grammar] Name 3 ways to simplify a context-free grammar.
Eliminate ε−productions Production rule A → ε.Eliminate unit productions Production rule A → B where both A and B are variables.Eliminate useless productions Variable that's non-reachable or non-generating. We can simplify a grammar substantially by using the three kinds of simplifications together. But we have to be careful about the order. A possible problem is that, while we are eliminating some kind of unwanted productions, we may be introducing new unwanted productions of another kind.
[Context-free grammar] What does CNF stand for?
Chomsky Normal Form
[Context-free grammar] What form are these grammars in?
These grammars are in Chomsky Normal Form.
[Context-free grammar] What's the advantage of the Chomsky Normal Form?
Any derivation of a string of length n takes exactly 2n − 1 steps. For example, derivation of abc takes exactly 5 steps:
[Context-free grammar] What's an ε−production VS nullable production?
ε−production: A → ε. A yields ε.nullable production: A eventually leads to ε. A derives ε.
Which entities can represent: regular language VS context-free language
regular language - DFA, NFA, regular expressions DFA - Deterministic Finite Automaton, NFA - Nondeterministic Finite Automatoncontext-free language - PDA, CFG PDA - Pushdown Automaton, CFG - Context-Free Grammar
You're at a state q1. How to find the ε-closure of this state?
Find all states this state possibly leads to with ε.
[NFA - DFA equivalence] Name 3 steps for turning your NFA to DFA.
Find the initial state (ε-closure). Find δ(qinitial state, 0) = ___ and δ(qinitial state, 1) = ___. Move on to other states.
What does PDA stand for?
Pushdown Automaton
[Pushdown Automaton] What's a simplistic description of a PDA?
Pushdown Automaton = NFA + stack (LIFO)
[Pushdown Automaton] Why is the Pushdown Automaton (PDA) called so?
Because writing a symbol to the stack == pushing.
[Pushdown Automaton] What's Г in the transition function of the PDA? Transition function of the Pushdown Automaton (PDA).
Г is the stack alphabet.
[Pushdown Automaton] How to read this transition function?
Same as in NFA, except: given: what you pop from the stack result: what you push to the stack Given: You are in state q1 You read input "a" You pop "1" from the stack Result: (q2, 0) Go to state q2 Push "0" to the stack (q3, ε) Go to state q3 Push nothing to the stack
[Pushdown Automaton] What does this notation mean?
Given input a, and pop b We push ε
[Pushdown Automaton] What are the 2 PDA requirements for the string to be accepted?
We're at an accept state The stack is empty
[Context-Free Grammar] Why are Context-Free Grammars called context-free?
Because the context surrounding LHS variable does not matter.
[Context-Free Grammar] Is this language context-free?
CFG (Context-Free Grammar)PDA (Pushdown Automaton)
[Context-Free Grammar] Is this language context-free?
No. We can't rememeber 2 types of things at the same time. Push is "remember", pop is "use".
[Context-Free Grammar] Is this language context-free?
No. We can only pop n once. Push is "remember", pop is "use".
[Context-Free Grammar, Pushdown Automaton] Describe what CFG is 'all about' and what PDA is 'all about'. Context-Free Language
CFG is all about wrapping. PDA is all about pushing to the stack, and then popping from the stack.
[CFG-PDA equivalence] Name 2 steps to turn CFG into PDA?
Rewrite your CFG to A → aBCD form That is, the right-hand side begins with a single terminal and continues with zero or more variables.Build a PDA that: for input 1 & pop S - pushes SAA for input 0 & pop S - pushes B Push SA means first push A and then push S.
[CFG-PDA equivalence] What's the analogy between this CFG and PDA's: input string what we pop from the stack what we push to the stack Context-Free Grammar
Build a PDA that: for input 1 & pop S - pushes SAA for input 0 & pop S - pushes B Push SA means first push A and then push S.
[Closure properties of Context-Free Languages] How would you prove that if A and B are context-free, then A ∪ B is context-free?
[Turing Machine] What's the obvious way to determine whether your TM accepts the input string? If you're standing on a Turing Machine tape, and you're given some input.
Zig-zag to the corresponding places on the two sides of the # and determine whether they match.
[Turing Machine] How to read the transition function of the TM?
Given: state q input a Result: go to state r write b (replacing a) move to the L That is, when the machine is in a certain state q and the head is over a tape square containing a symbol a, the machine writes the symbol b replacing the a, and goes to state r. The third component is either L or R and indicates whether the head moves to the left or right after writing. In this case, the L indicates a move to the left.
[Turing Machine] Why don't we have an explicit input we feed into the Turing Machine? The automaton that we use as a Turing machine will have neither an input file nor any special output mechanism. Whatever input and output is necessary will be done on the machine's tape.
Tape-only automaton is easier to describe. We don't have an 'input string' anymore, we have 'what the tape initially contains'.
[Turing Machine] What is this symbol □ called?
A blank.
[Turing Machine] What's a, b, R?
a - read (the current tape symbol), b - write (the symbol that replaces it), and R - to the right (the direction in which the read-write head is to move). Given: state q, input aResult: go to state r, write b (replacing a), move to the L
[Turing Machine] On this picture - where are the states, and where is the input string? a - the current tape symbol,b - the symbol that replaces it, andR - the direction in which the read-write head is to move. Given: state q, input aResult: go to state r, write b (replacing a), move to the L
The states are in the 'control unit' The input string is 'some part of the initial tape state'
[Turing Machine] How would you approach recognizing a language of palindromes with a TM? L = { 110011, 101, all palindromes }
[Turing Machine] Given abbbba input on a tape - how would you go state to state? A TM that recognizes a language of palindromes.L = { 110011, 101, all palindromes }
[Turing Machine] Where does the δ function (transition function) hide in this picture?
'Control Unit' is where the δ function, and the current state hide.
[Variants of Turing Machines] How would you simulate a doubly-infinite TM on our semi-infinite TM? Our TM is semi-infinite (in the Emre Sermutlu book).
[Variants of Turing Machines] How would you simulate a multitape TM on our semi-infinite TM? Our TM is semi-infinite (in the Emre Sermutlu book).
[Variants of Turing Machines] How would you simulate a two-dimensional TM on our semi-infinite TM? Our TM is semi-infinite (in the Emre Sermutlu book).
Again, there are many details we have to think about during implementation. For example, 3 could be represented as 111. For the minus sign, we need another special symbol.The multidimensional TM will find the neighbor of a cell easily, by going one unit left, right, up, or down. The 3−tape machine must search through the whole tape for correct coordinates.But all these details about efficiency are unimportant from our current point of view. These machines recognize the same languages.
[Universal Turing Machine] We can represent a DFA with a string. What does R and A mean in this string?
A - accept (state) R - reject (state)
[Turing Machine] Give an example of both: TM that is like a computer program TM that is like a computer
TM that is like a computer program - palindrome recognizer TM that is like a computer - Universal Turing Machine (UTM) Universal Turing Machine has 3 tapes: One for the TM it will simulate, one for the input, and another to keep the current state in memory.
[Universal Turing Machine] What each of the 3 tapes is used for in the UTM? The UTM can simulate any TM, in other words, any computer!
Tape 1 - Turing Machine description One for the TM it will simulateTape 2 - input One for the inputTape 3 - given TM state Another to keep the current state in memory During the computation, the contents of tapes 2 and 3 will change.Tape 1 is fixed. At the end of the computation, the output will be on tape 2.
[Turing Machine] What automatons can loop? DFAs Deterministic Finite AutomatonsPDAs Pushdown AutomatonsTMs Turing Machines
DFAs - always result in ACCEPT or REJECT Deterministic Finite AutomatonsPDAs - always result in ACCEPT or REJECT Pushdown AutomatonsTMs - CAN LOOP Turing Machines do not always give the result ACCEPT or REJECT.Sometimes they continue the computation indefinitely, in other words, they LOOP. This is a situation we have not encountered for DFAs or PDAs.Clearly, this TM accepts 1111 and rejects 0011. What about 1100?
[Turing Machine] What's a decider Turing Machine?
TM that halts (results in ACCEPT or REJECT) on all inputs.
[Turing Machine] What's a Turing-decidable language?
A language for which there exists a decider TM that accepts it.
[Turing Machine] Decider TM vs Recognizer TM for some language L? Theory: you can't have a "decider Turing machine", you can have a "decider Turing machine for some language".
[Turing Machine] What dilemma does using a recognizer TM put you into?
Is it goint to accept if we wait long enough?
[Turing Machine] Turing machine (TM) vs Universal Turing Machine (UTM)?
UTM is a TM with a particular transition function. A "Universal Turing machine" is one whose input consists of a description M of some arbitrary Turing machine, and some input w to which machine M is to be applied, we write this combined input as M + w.This produces the same output that would be produced by M.
[Turing Machine] Name 3 different methods of describing a Turing Machine: low-level medium-level high-level
low-level - using a diagram similar to PDA medium-level - description using pseudocode high-level The lower the level, the more complicated the description.
[Decidability] What does the notation〈O〉mean?
The string representation of the object O.
[Decidability] What 'data type' can be decidable or undecidable?
Languages (sets of strings).
[Decidability] What exactly is asked in this question?
Given a DFA D and a string w, can a TM determine if w is accepted or rejected by D in finite time.