There are three different terms,
1. language
2. language generator (grammar of the language)
3. language recognizer (machine (automaton))
- language are represent in the form of expressions (regular expression, context-free expression)
- grammar specified rules for generating the language.
- automaton is a machine that recognize the language.
Pumping lemma is useful for proving a language is not CFL or RL.
Basic Idea:
- If the language size is finite, then it is obvious. (RL)
- If the language size is not finite, then by pigeonhole, there must be part of the rule reused.
- This reuse of rule lead to loop in the path, then remove such loop, or repeat multiple times should not affect acceptance of the string.
Definition A finite automaton is a 5-tuple
$(Q, \Sigma , \delta, q_0 F)$ , where
- Q is a finite set called the states.
$\Sigma$ is a finite set called the alphabets.$\delta : Q \times \Sigma \rightarrow Q$ is the transition function.$q_0 \in Q$ is the start state$F \subseteq Q$ is the set of accept states.A nondeterministic finite automaton allow
$\epsilon$ transition, that is, 3.$\delta : Q \times \Sigma_\epsilon \rightarrow Q$ is the transition function.
Theorem Every nondeterministic finite automaton has an equivalent deterministic finite automaton.
Finite automaton is the recognizers for equivalent Regular Languages. Another words, Regular Languages are exactly the languages accepted by (non)deterministic finite automata;
Definition Formal definition for Regular Expression if R is
$a$ for some$a$ in the alphabet$\Sigma$ ,$\epsilon$ $\empty$ $(R_1 \cup R_2 )$ , where$R_1$ and$R_2$ are regular expressions,- (R 1 ◦ R 2 ), where
$R_1$ and$R_2$ are regular expressions, or$(R_1^* )$ , where$R_1$ is a regular expression. In items 1 and 2, the regular expressions a and ε represent the languages {a} and {ε}, respectively. In item 3, the regular expres- sion ∅ represents the empty language. In items 4, 5, and 6, the expressions represent the languages obtained by taking the union or concatenation of the languages R 1 and R 2 , or the star of the language R 1 , respectively.
To differentiating regularities, we can use Pumping lemma
Pumping Lemma If
$A$ id a regular language, then there is a number$p$ (the pumping length) where if$s$ is any string in$A$ of length at least$p$ , then$s$ may be divided into three pieces,$s = xyz$ , satisfying the following conditions:
- for each
$i \geq 0$ ,$xy^iz \in A$ ,$|y| > 0$ , and$|xy| \leq p$ .
The proof is really trivial (based on pigeonhole principle).
The pumping lemma is useful when you try to prove a language is not regular. But this theorem is not really useful if you try to prove a language is regular. The pumping lemma is a one way statement, says nothing about non-regular language. Showing second part is not sufficient for proving the language is regular.
To prove a language is regular, one can start from the definition, or its equivalent models.
- Start with proof by contradiction.
- Choose a particular string, with length
$\geq p$ . (choose a string that break the rule when pump). - Then use the fact that
$|xy| \leq p$ , to help you break the pumpable property - Last, show for which choice of
$i$ in$xy^iz$ where such property break.
Example Show that
$AB1 = {a^ib^j : i \geq j}$ is not regular.note: we want to break the property where
$i \geq j$
- A assume
$AB1$ is regular.- Let
$\omega = "a^nb^n"$ //setting a, b length equal to each other still in the language. then we break it by pump away a to make first part smaller.- Then by definition
$xy = a^m$ , where$m \leq n$ must be true.- let
$i = 0$ , contradiction. QED
Second approach for proving non-regular: use the definition, show that the language is not closed under Concatenation, Union or Kleene star.
1. show inherently ambiguous
2. if language is generatable, can you always built equivalent machine recognize it?.
3. complete example when review for exam
Definition CFG is 4-tuple
$(V, \Sigma, R, S)$
- V is a finite set called variables
$\Sigma$ is a finite set called terminals (disjoint from V).- R is a finite set of rules
$S \in V$ is a start varible.
Definition A context free laguage is any language that is generated by a context-free grammar. (CFL)
Definition A string
$\omega$ is derived ambiguously in context-free grammar G if it has two or more different leftmost derivations. Grammar G is ambiguous if it generates some string ambiguously.*leftmost derivation: if at every step the leftmost remaining variable is the one replaced.
Theorem Any CFL is generated by a CFG in Chomsky normal form
Definition A pushdown automaton is a 6-tuple
$(Q, \Sigma, \Gamma , \delta, q_0, F)$ , where$Q, \Sigma, \Gamma$ , and$F$ are all finite sets, and
$Q$ is set of states$\Sigma$ is the input alphabet,$\Gamma$ is the stack alphabet,$\delta : Q \times \Sigma_\epsilon \times \Gamma_\epsilon \rightarrow P(Q \times \Gamma_\epsilon)$ is the transition function.$q_0 \in Q$ is the start state.$F \subseteq Q$ is the set accept states.
Theorem 2.20 A language is context free if and only if some pushdown automaton recognizes it.
The proof for above theorem is tedious, basically it's a proof by construction, where it shows that start from one of it you can construct the other one.
Pumping Lemma for Context-Free Languages If
$A$ is context-free language, then there is a number$p$ (the pumping length) where, if$s$ is any in$A$ of length at least$p$ , then$s$ may be divided into five pieces$s = uvxyz$ satisfying the conditions,
- for each
$i \geq 0$ ,$uv^ixy^iz \in A$ $|vy| > 0$ $|vxy| \leq p$ .
The pumping length has upper bound
Example
1.go through TM examples in ch 3.1
Definition A Turing machine is a 7-tuple,
$(Q, Σ, Γ, δ, q_0 , q_{accept} , q_{reject} )$ , where$Q, Σ, Γ$ are all finite sets and
$Q$ is the set of states,$Σ$ is the input alphabet not containing the blank symbol ␣ ,$Γ$ is the tape alphabet, where$␣ ∈ Γ$ and$Σ ⊆ Γ$ ,$δ : Q × Γ \rightarrow Q × Γ × {L, R}$ is the transition function,$q_0 ∈ Q$ is the start state,$q_{accept} ∈ Q$ is the accept state, and$q_{reject} ∈ Q$ is the reject state, where$q_{reject} \neq q_{accept}$
Turing Machines computation process are represented by configuration. Configuration describes TM's current state, the current tape contents, and the current head location. The transition function
typically configuration are represented as
$u q v$ , where$uv$ is the input string. The$q$ represent the current state of TM. and the head of TM is pointed to the first symbol of string$v$ .
Definition Call a language Turing-recogniziable if some Turing machine recognizes it.
Definition Call a language Turing-decidable or simply decidable if some Turing machine decides it.
The difference between deciadable and recognizable is that, for Turing decidable, there are a turing machine that recognize such language and it always accept or reject, never halts. Turing-Recognizable only guarantee that if string is in such language than turing machine accepts it, said nothing about what happen if machine does not accept it. (Both halt and reject is possible).
The Turing machine have very high level of robustness. This basically means that the original turing machine model have equivalence expressing power (recognize) compare to its reasonable variants (those variants may seems more powerful, but we can show that all the add-on "features" can be simulated with original turing machine.)
Here are some example variants that are equivalence to the Turing machine.
- multitape turing machine (Thm 3.13)
- non-deterministic Turing machine (Thm 3.16)
- stay put turing machine.
In general, one can demonstrate the equivalence by showing that the variant part can be simulates using plain Turing Machine. (see section 3.2, for details)
> TODO read scan turing 1936, then add more detail here
The Church-Turing thesis provides the definition of algorithm. This fomalized the intuitive notion of algorithms.
When talking about algorithm or more specifically Turing Machine Algorithm. There are three different level of description.
- formal description: use the definition of turing machine, write out every details, includes transitions functions and states etc.
- Implementation description: use more simple english descprition for how Turing machine's head move and the way that its stores data, etc.
- high level description: you can think of it as pseudo code.
The previous section (algorithm) implies that: Asking whether certain Turing Machine algorithm exist for a problem, is same as asking whether such problem is Turing-Decidable.
Theorem 4.1
$A_{DFA}$ is decidable language. Theorem 4.2$A_{NFA}$ is decidable language Theorem 4.3$A_{REX}$ is decidable language.
Then, asking whether such acceptance problem is decidable by Turing-Machine is same asking whether language
To determine whether such language is decidable, we can show that there exist a TM M that decides
Theorem 4.1-3 are essentially equivalent. One can convert NFA or REX to DFA then use DFA as part of the input, then 2 and 3 are obviously true.
Theorem 4.4
$E_{DFA}$ is decidable language.
Theorem 4.4 can be prove using iterative marking algorithm. Starting from initial state, mark it. Then mark all state with marked state as incoming state. Finally accept is no accept state is marked. Otherwise, reject.
Theorem 4.5
$EQ_{DFA}$ is a decidable language.
Theorem 4.5 state that determine whether two DFAs are equivalent is decidable. The proof idea: If DFA A and B is not equivalent, then there must be strings that only accept by either A or B. (known as symmetric difference of A and B).
then if both DFA is equivalent, we know their symmetric difference must be empty. Therefore proving A and B are equivalent is same as deciding
Theorem 4.7
$A_{CFG}$ is a decidable language.
Theorem 4.8
$E_{CFG}$ is a decidable language.$E_{CFG} =$ {$$ | G is a CFG and$L(G) = \empty$ }
The basic idea for proving emptiness problem for CFG is to follow marking algorithm. You start from terminals of CFG, then reach up, see whether eventually the start symbol got marked. If start symbol marked then basically it means there is a way that start symbol can reach terminals. Hence, reject.
Theorem 4.9 Every context-free language is decidable.
We can use the machine from Thm 4.7, then put the desired CFG as input, we can decide whether a string is belong to such CFL.
Fact
$EQ_{CFG}$ is not decidable, proof will be shown in next chapter.
Decidable Summary
From Thm 4.9, we now know that:
There are correponding recognizer machine for regular and context free language. For decidable language, it's recognizer is basically the corresponding turing machine that always halts.
Theorem 4.11
$A_{TM} = {<M,w>| m \text{ is a } TM \text{ and }M \text{accepts } w}$ $A_{TM}$ (acceptance problem of turing machine) is undecidable.
The proof technique for Thm 4.11 is prove by contradiction. We reduce acceptance problem to Diag, which is a machine that always reject itself.
We can construct a correspondence between set of all languages and an uncountable set, and we can also show that set of all turing machine is countable. Hence, there must exist turing unrecognizable languages.
TODO: how is this related to Thm 4.11 A_tm?
Definition A language is co-Turing-Recognizable if it is the complement of a Turing-recognizable language.
Theorem 4.22 A language is decidable iff it is Turing-recognizable and co-Turing-recognizable.
The basic idea is that the any string must either be in language A or its complement, hence one of the two machine must accept the string. Therefore, always halts.
Theorem 5.1 Halting problem of turing machine is undecidable
Proof Idea: reduction from acceptance problem to halting problem.
Theorem 5.2 Empty problem of turing machine is undecidable
$E_{TM} = { | M \text{ is a } TM \text{ and } L(M) = \empty}$ $E_{TM}$ is undecidable.
Proof Idea: reduction from acceptance problem to emptiness problem. Idea for constructing acceptance machine based on emptiness machine: run emptiness machine on input SIM_M_w, where SIM_M_w is a string describes running w on machine M. If emptiness machine reject, then M must accepted w.
Theorem 5.3
$REGULAR_{TM} = { | M \text{ is a } TM \text{ and } L(M) \text{ is a regular language}}$ $REGULAR_{TM}$ is undecidable.
Proof Idea: still use reduction from acceptance problem to regular language decider. The idea is to map input M to a new machine M1, such that this new machine recognize regular language if and only if M accept w.
Fact Rice Theorem states that determining any property of the languages recognized by Turing machine is undecidable
TODO read rice theorem proof
Theorem 5.4
$EQ_{TM} = { <M_1, M_2>| M_1 \text{ and } M_2 \text{ are } TMs \text{ and } L(M_1) = L(M_2)}$ $EQ_{TM}$ is undecidable.
Proof Idea: One should realize that
The computation history method is an important technique for proving that
Definition 5.5 Let M be a Turing machine and w an input string. An accepting computation history for M on w is a sequence of configurations,
$C_1 , C_2 , . . . , C_l$ , where$C_1$ is the start configuration of M on w,$C_l$ is an accepting configuration of$M$ , and each$C_i$ legally follows from$C_{i−1}$ according to the rules of$M$ . A rejecting computation history for$M$ on$w$ is defined similarly, except that$C_l$ is a rejecting configuration.
Definition 5.6 A Linear Bounded Automation or
$M_{LBA}$ is a restricted type of Turing machine wherein the tape head isn’t permitted to move off the portion of the tape containing the input. If the machine tries to move its head off either end of the input, the head stays where it is—in the same way that the head will not move off the left-hand end of an ordinary Turing machine’s tape.
Despite their memory constraint,
Lemma 5.8 Let M be an LBA with q states and g symbols in the tape alphabet. There are exactly
$qng^n$ distinct configurations of M for a tape of length n.
Theorem 5.9
$A_{LBA} = {<M,w> | M \text{ is an } LBA \text{ that accepts string } w}$ $A_{LBA}$ is decidable.
Note that this is different from turing machine, where acceptance problem is undecidable for regular turing machine. But thanks to lemma 5.8, we know there are only finite amount of distinct configurations, therefore, if machine still run after that much steps, then the machine must be in some loops therefore never accept.
Theorem 5.10
$E_{LBA}$ is undecidable.
Proof Idea: The proof using reduction from
Theorem 5.13 $ALL_{CFG}$ is undecidable.
TODO read proof.
Notes: We say problem A is reducible to problem B, that means there is a transformation function that convert instance of A to instance of B. Then if you can solve problem B, similarily you solved problem A. When question is concerning decidability of problem B, we can start by assuming there is decider for B, then try to come up with reduction that can reduce some undecidable problem A to B. In such way, we constructed a contradiction proof.
Definition 5.17 > A function $f : \Sigma^* \rightarrow \Sigma^*$ is a computable function is some turing machine $M$, on every input $w$, halts with just $f(w)$ on tape.
Definition 5.20 (Formal definition of mapping reducibility) Language A is mapping reducible to language B, written $A ≤_m B$, if there is a computable function $f : Σ^∗ → Σ^∗$ , where for every $w$, $w ∈ A ⇐⇒ f (w) ∈ B$ The function $f$ is called the reduction from A to B.
Theorem 5.22 If $A ≤_m B$ and B is decidable, then A is decidable.
Corollary 5.23 If $A ≤_m B$ and A is undecidable, then B is undecidable.
Watch out the difference between 5.22 and 5.23.
Theorem 5.28 If $A ≤_m B$ and B is Turing-recognizable, then A is Turing-recognizable.
Corollary 5.29 If $A ≤_m B$ and A is not Turing-recognizable, then B is not Turing-recognizable.
Notes: From Thm 4.22, we know that $A_{TM}$ can not be co-Turing-recognizable, or $\overline{A_{TM}}$ is not Turing recognizable. Also, the mapping reducibility $A \leq_m B$ implies $\overline{A} \leq_m \overline{B}$. GIven two facts above, we can use Corollary 5.29 above to show that B is not Turing-recognizable by showing $A_{TM} \leq_m \overline{B}$. This implies that $\overline{A_{TM}} \leq_m B$, then Corollary 5.29 state that B must be not Turing-recognizable.
Theorem 5.30 $EQ_{TM}$ is neither Turing-recognizable nor co-Turing-recognizable.
Proof Idea: The proof use two reduction, one reduce $A_{TM}$ to $\overline{EQ_{TM}}$, ther other reduce $A_{TM}$ to $EQ_{TM}$.
Written with StackEdit.