2010计算理论课件(ppt概述)

3
4
5
6
()
2 / 24
Outline
1
Regular Language Context-free Language(CFL) Turing Machine and Recursive Enumerable Language Undecidablity P and N P Problems N P Complete Problems
()
7 / 24
Context-free Language
Example: Show that language L = {ai b j c k | j ≥ i + k} is context-free. Solution: {ai b j c k | j ≥ i + k} = ai b i b b k c k Language L can be generated by the following CFG: S → XYZ , X → aXb, Y → bY , Y → bYc, X → e, Y → e, Z → e
()
4 / 24
Regular Language
2.4.8 Are the following statements true od false? Explain you answer in each case. (P 91) Every subset of a regular language is regular. (F) Every regular language has a regular proper subset. (F) (Hint: ) If L is regular, then so is {xy | x ∈ L and y ∈ L}. (T) (Hint:{xy | x ∈ L and y ∈ L}=L L) {w | w = w R } is regular. (F) If L is regular, then so is {w | w ∈ L and w R ∈ L}. (T) (Hint: L = L ∩ LR .) If C is any set of regular languages, then ∪C is a regular language. (F) {xyx R | x, y ∈ Σ } is regular. (T) (Hint: {xyx R | x, y ∈ Σ } = Σ . By letting x = e, y can vary over all the strings of Σ .)
() 5 / 24
Outline
1
Regular Language Context-free Language(CFL) Turing Machine and Recursive Enumerable Language Undecidablity P and N P Problems N P Complete Problems
2
3
4
5
6
()
3 / 24
Regular Language
Regular Expression Deterministic nite automata(DFA) Non-deterministic nite automata(NFA) Closure properties and Pumping Theorem State Minimization (graduated course)
Review: Elements of Computation Theory
XIAOGANG JIN
AI Institute, College of Computer Science Zhejiang University E-Mail: xiaogangj@
()
1 / 24
()
11 / 24
Context-free Language
3.5.14 Which of the following languages are context-free? Explain briey in each case. a) {am b n c p | m = n or n = p or m = p} This language is context-free. {am b n c p | m = n or n = p or m = p} = {am b n c p | m = n} ∪ {am b n c p | n = p} ∪ {am b n c p | m = p} and {am b n c p | m = n} = {an b n } c {am b n c p | n = p} = a {b n c n } {am b n c p | m = p} can be generated by the following CFG: {S → aSb, S → T , T → cT , T → e}.
Question:
Give a context-free language Context-free Grammar Give a context-free language PDA Give a context-free grammar PDA (Lemma 3.4.1, Example 3.4.1 P 136) Show a given language be context-free or non-context free?
()
4 / 24
Regular Language
Regular Expression Deterministic nite automata(DFA) Non-deterministic nite automata(NFA) Closure properties and Pumping Theorem State Minimization (graduated course)
b) {a, b} {an b n : n ≥ 0} This language cab be expressed as {am b n | m = n} ∪ Σ aΣ bΣ aΣ ∪ Σ bΣ aΣ bΣ
()
10 / 24
Context-free Language
3.5.8 Show that the language {ww | w ∈ {a, b} } is not context-free. Proof: Let L = {ww | w ∈ {a, b} }, and s = ap b p ap b p , s ∈ L. p is the pumping length. Use the Pumping Theorem to prove that. If L is CFL, such that s = uvxyz, |vxy | ≤ p. (1) Consider that the substring vxy of s is over the midpoint of s. Pump the s as uxz, the string s is as ap b i aj b p form, where i and j are not equal to p at the same time. Such that the s is not the form ww . (2) If vxy is placed before the midpoint of s, by the Pumping Theorem, when s = uv 2 xy 2 z, the b has to be put the rst place of the last part of s after the midpoint, such that the s is not the form ww . Similarly, if vxy is placed after the midpoint of s, when s = uv 2 xy 2 z, the a has to be moved to the last place of the rst part of s before the midpoint, also the s is not the form ww . So, L is not CFL .
1
Regular Language Context-free Language(CFL) Turing Machine and Recursive Enumerable Language Undecidablity P and N P Problems N P Complete Problems
2
2
3
4
ห้องสมุดไป่ตู้
5
6
()
6 / 24
Context-free Language
Context-free Grammar(CFG) Pushdown automata Closure properties and Pumping Theorem
()
7 / 24
Context-free Language
Context-free Grammar(CFG) Pushdown automata Closure properties and Pumping Theorem
()
8 / 24
Context-free Language
3.1.9 Show that the following language are context-free by exhibiting context-free grammars generating each (P 122): {am b n | m ≥ n} {S → aSb, S → aS, S → e} {am b n c p d q | m + n = p + q} Let m + n = p + q = N, then n = N m, p = N q. am b n c p d q = am b Nm c Nq d q In case of m ≥ q, am b n c p d q = aq amq b Nm c Nm c mq d q S → aSd, S → A, A → aAc, A → B, B → bBc, B → e In case of m < q,we can obtain the similar results. {w ∈ {a, b} : w has twice as many b’s as a’s } {S → e, S → Sabb | aSbb | abSb | abbS, S → Sbab | bSab | baSb | babS, S → Sbba | bSba | bbSa | bbaS } {uawb : u, w ∈ {a, b} |u| = |w |} {S → Tb, T → aTa, T → aTb, T → bTa, T → bTb, T → a}