Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
Lecture Nine: A Hierarchy of Formal Languages and Automata
1. Recursive and recursively enumerable languages 2. Unrestricted grammars 3. Context-sensitive grammars and languages 4. The Chomsky hierarchy 5. Tutorial questions
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
1 Recursive and recursively enumerable languages We have known that Turing machines are very powerful and can accept non-context-free languages. A nature question is: Are there more complex languages that Turing machines cannot accept? Denition. A language L is called recursively enumerable if there exists a Turing machine that accepts it. If L is a recursively enumerable language, then there is a Turing machine M such that for each w L, q0 w
M
x1 qf x2 .
Question: if a w L, what will happen to the Turing machine? The Turing machine may halt on a non-nal state, or goes to an innite loop. Class discussion
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
Denition. A language L on is called recursive if there exists a Turing machine M that accepts L and that halts on every w + . That is there is a membership algorithm for L (note that an algorithms always halts). Observation:
Recursively Regular L1 Contextfree L2 Recursive L3 enumerable L4
Figure 1: Four classes of languages: L1 L2 L3 L4 .
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
Enumeration on a set: Given a set S, there is a procedure to list all elements of S in such an order: e1 , e2 , , en , which corresponds to the order of positive numbers 1, 2, , n, . The importance of enumeration property for a set. Class discussion How can we construct an enumeration procedure for a recursive language? Step 1. Construct a Turing machine M to generate all strings on + in some order w1 , w2 , ; Step 2. Construct a Turing machine M that takes all strings generated by M as input one by one; Step 3. If a w L, then write w on the tape of M , if w L, M does not write it on its tape (note that this is always feasible, why? Class discussion)
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
How can we construct an enumeration procedure for a recursively enumerable language? What is the key difference between recursive languages and recursively enumerable languages? Class discussion The previous procedure does not work for recursively enumerable languages. Why? Class discussion
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
Step 1. Get M to generate one string w1 + ; Step 2. Take w1 as input, get M to only execute one move for w1 ; Step 3. Back to M to generate another w2 + ; Step 4. Take w2 as input, get M to only execute one move for w2 ; Step 5. Back on w1 , get M to execute the second move for w1 ; Step 6. Back to M to generate another w3 + ; What is the consequence of this procedure?
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
w1 a1 a2 a3 ... first move second move third move
w2 b1 b2 b3 ...
w3 c1 c2 c3 ...
w4 d1 d2 d3 ...
Figure 2: Contors diagonal approach. Class discussion
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
languages that are not recursively enumerable Countable set: a set is either nite or having 1-1 corresponding with the set of positive integer. Theorem. Let S be an innite countable set. Then its power set 2S is not countable. Proof. Proof by contradiction. Suppose 2S is countable. Then We assume that we can list each element of 2S as {t1 , t2 , }. Since S is countable, we can write S = {s1 , s2 , , }. Then each element of 2S is a subset of S, which we encode as a binary string: e.g. {s1 , s3 , s5 } is encodded as 1010100 . Then each of t1 , t2 , is encodded as a different binary string.
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
t1
1 ...
t2 t3 t4
1 1 1
0 1 0
0 1 0
0... 0... 1... This string does not in the set 2 S !
1011.....
0100...
Figure 3: Contors diagonal approach for showing 2S is not countable. Class discussion
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
10
Theorem. For any nonemptyset , there exist languages that are not recursively enumerable. Proof. A language is a subset of , and each this subset is a language. So 2 is the set of all languages. From the previous result, we know that 2 is not countable. But from the denition, all languages on accepted by Turing machines are recursively enumerable, so the set S of all languages on accepted by Turing machines are also countable. Why? Consider using Contor diagonal approach to show that. 2 , and S is countable and 2 is not countable, this Since we have S implies there are non-recursively enumerable languages in 2 . Why? Class discussion
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
11
2 Unrestricted grammars Denition. A grammar G = (V, T, S, P ) is called unrestricted if all the productions are of the form u v, where u (V T )+ and v (V T ) . Theorem. Any language generated by an unrestricted grammar is recursively enumerable. Proof. We give a procedure that can enumerate all strings in language L(G), where G is an unrestricted grammar. (1) We can list all w that are derived from Gs productions in one-step: S w. Note G only contains nite productions, so all these w are nite, and can be listed. (2) We can also list all w L(G) that are derived in two-steps: S x w. In this way, we can simulate these derivations on a Turing machine. So the language is recursively enumerable.
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
12
Theorem. For each recursively renumerable language L, there exists an unrestricted grammar G such that L = L(G). Proof idea. We are given a Turing machine M = (Q, , , , q0 , , F ), then we want to construct an unrestricted grammar G satisfying L(G) = L(M ). (1) Recall that the computation of a Turing machine can be described as a sequence of instantaneous descriptions (id): q0 w
xqf y.
(2) We dene a grammar such that q0 w xqf y iff q0 w
xqf y.
(3) From q0 w xqf y, we need to show S w for all w satisfying q0 w xqf y (i.e. w L(M )).
Then we will have S q0 w xqf y w.
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
13
Example. Let M = (Q, , , , q0 , , F ) be a Turing machine where Q = {q0 , q1 }, = {a, b, }, = {a, b}, F = {q1 } and (q0 , a) = (q0 , a, R), (q0 , ) = {q1 , , L). The computation of aa is as follows: q0 aa aq0 a aaq0 aq1 a .
Question: what is the language accepted by this Turing machine? Class discussion
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
14
3 Context-sensitive grammars and languages Denition. A grammar G = (V, T, S, P ) is called context-sensitive if all productions are of the form: x y, where x, y (V T )+ and |x| |y|. Why is such grammar called context-sensitive? Theorem. All productions of any context-sensitive grammar can be writen in a normal form: xAy xvy where A V . This results implies that a rule like A v can only be applied in a context where x is on the left and y is on the right. So it is context-sensitive.
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
15
context-senistive languages and linear bounded automata Denition. A language L is called context-sensitive if there exists a context-sensitive grammar G such that L = L(G) or L = L(G) {}. Why do we introduce empty string into the denition of context-sensitive language? Recall what is the denition of the language accepted by a Turing machine? No empty string included! How about context-free languages? Class discussion
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
16
Example. Consider a context-sensitive grammar: S abc|aAbc, Ab bA, Ac Bbcc, bB Bb, aB aa|aaA. Consider derivation of a4 b4 c4 - Class discussion
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
17
non-deterministic Turing machines and linear bounded automata (Chapter 10) Denition. A nondeterministic Turing machine is an automaton where the transition function is dened as : Q 2Q{L,R} . Example. A Turing machine has transitions specied as (q0 , a) = {(q1 , b, R), (q2 , c, L)}. This Turing machine is nondeterministic. The moves q0 aaa q0 aaa q2 caa are both possible. bq1 aa and
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
18
Denition. A linear bounded automaton is a nondeterministic Turing machine M = (Q, , , , q0, , F ), with the restriction that two symbols [ and ] are in , and (qi , [) contains only elements of the form (qj , [, R), and (qi , ]) contains only elements of the form (qj , ], L). A string w is accepted by a linear bounded automaton if q0 [w] for some qf F , x1 , x2 .
[x1 qf x2 ]
Theorem. A language not containing is context-sensitive iff there is a linear bounded automaton M such that L = L(M ).
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
19
relation between recursive and context-sensitive languages Theorem. Every context-sensitive language is recursive. But There exists recursive language that is not context-sensitive. Proof. We rst prove the statement every context-sensitive language is recursive. (1) Suppose for each w L(G), we have the derivation S x1 xn w. Note that for each j |xj | |xj+1 | |w| (why?) (2) Since in each step, there are only nite possible productions to apply to at most |V T | symbols, and the length of w is |w|, so altogether, the derivation length is bounded by |w||P ||V T |. (3) From (2) we can design a membership algorithm for L: for any given w + , check all derivations with length up to |w||P ||V T |. If one of these derivations gives w, then w L, otherwise w L. This concludes L is recursive. Why?
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
20
Now we prove statement There exists a recursive language that is not context-sensitive. (1) Consider the set of all context-sensitive grammars on T = {a, b}. Suppose each grammar has variable set {V0 , V1 , }, and productions are of the string form: x y 1 ; x2 y 2 ; , x m y m . (2) To this string, apply homomorphism: h(a) = 010, h(b) = 012 0, h() = 013 0, h(; ) = 014 0, h(Vi ) = 01i+5 0 So any context-sensitive grammar can be represented by a string from L((011 0) ). Why? Class discussion
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
21
(3) We introduce an ordering on {0, 1}+ so that we can write strings in order w1 , w2 , . (How to do it? - hint: the number of strings with a xed length from {0, 1}+ is always nite ) If a string wj from {0, 1}+ denes a context-sensitive grammar, we call grammar Gj . (4) We dene a language L = {wi : wi denes a context-sensitive grammar Gi and wi L(Gi )}. What do these wi look like? Class discussion
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
22
(4) L is recursive. Why? We can give a membership algorithm for L: Given wi {0, 1}+ , we can check if wi denes context-sensitive grammar Gi (how to check?); if yes, then wi L, otherwise wi L. (5) We now show L is not context-sensitive. Assume L is context-sensitive, then there is some wj {0, 1}+ such that wj denes context-sensitive grammar Gj and L = L(Gj ). (6) Then we ask whether wj L(Gj ) or not. If wj L(Gj ), then by denition wj L. But we have L(Gj ) = L which leads to wj L contradiction! If wj L(Gj ), then by denition, we have wj L. Again, we have L = L(Gj ) which leads to wj L(Gj ) - contradiction again! (7) This concludes that L is not a context-sensitive language.
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
23
4 The Chomsky hierarchy
Regular L1
Contextfree L2
Contextsensitive L3
Recursively enumerable L4
Recursive
Figure 4: Chomsky hierarchy.
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
24
Deterministic Context-free languages (DCF - Chapter 7 & Lecture 7) Linear Context-free languages (LCF): Languages can be generated by linear context-free grammars. A linear context-free grammar is a context-free grammar where each production can only have at most one variable occurring in the right side (Chapter 3 & Lecture 3).
Context-free L
LCF L
Regular L
DCF L
Figure 5: Regular and context-free language classes.
Lecture Note for 300121 Formal Languages and Automata c UWS (Yan Zhang)
25
5 Tutorial questions 1. Exercises 16 and 17 on page 282. 2. Exercise 1 on page 288. 3. Exercise 1 (c) on page 294.
