The pumping lemma. Non regular languages.
October 30, 2017 | Author: Anonymous | Category: N/A
Short Description
Lemma. Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Non Regular ......
Description
Computational Models - Lecture 3 Non Regular Languages and the Pumping Lemma
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.1
Computational Models - Lecture 3 Non Regular Languages and the Pumping Lemma Algorithmic questions for NDAs
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.1
Computational Models - Lecture 3 Non Regular Languages and the Pumping Lemma Algorithmic questions for NDAs Context Free Grammars
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.1
Computational Models - Lecture 3 Non Regular Languages and the Pumping Lemma Algorithmic questions for NDAs Context Free Grammars
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.1
Computational Models - Lecture 3 Non Regular Languages and the Pumping Lemma Algorithmic questions for NDAs Context Free Grammars Sipser’s book, 1.4, 2.1, 2.2
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.1
if you can’t hear me
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.2
if you can’t hear me
you should move closer
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.2
if you can’t hear me
you should move closer
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.2
if you can’t hear me
you should move closer no functioning amplification equipment expected in the near future (next year or so)
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.2
Proved Last Time Thm.: A language, L, is described by a regular expression, R, if and only if L is regular.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.3
Proved Last Time Thm.: A language, L, is described by a regular expression, R, if and only if L is regular. =⇒ construct an NFA accepting R.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.3
Proved Last Time Thm.: A language, L, is described by a regular expression, R, if and only if L is regular. =⇒ construct an NFA accepting R. ⇐= Given a regular language, L, construct an equivalent regular expression.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.3
Negative Results We have made a lot of progress understanding what finite automata can do. But what can’t they do?
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.4
Negative Results We have made a lot of progress understanding what finite automata can do. But what can’t they do? Is there a DFA that accepts B = {0n 1n |n ≥ 0} C = {w|w has an equal number of 0’s and 1’s} D = {w|w has an equal number of occurrences of 01 and 10 substrings}
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.4
Negative Results We have made a lot of progress understanding what finite automata can do. But what can’t they do? Is there a DFA that accepts B = {0n 1n |n ≥ 0} C = {w|w has an equal number of 0’s and 1’s} D = {w|w has an equal number of occurrences of 01 and 10 substrings} Consider B: DFA must “remember” how many 0’s it has seen impossible with finite state. The others are exactly the same. Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.4
Negative Results Is there a DFA that accepts B = {0n 1n |n ≥ 0} C = {w|w has an equal number of 0’s and 1’s} D = {w|w has an equal number of occurrences of 01 and 10 substrings}
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.5
Negative Results Is there a DFA that accepts B = {0n 1n |n ≥ 0} C = {w|w has an equal number of 0’s and 1’s} D = {w|w has an equal number of occurrences of 01 and 10 substrings} Consider B: DFA must “remember” how many 0’s it has seen impossible with finite state.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.5
Negative Results Is there a DFA that accepts B = {0n 1n |n ≥ 0} C = {w|w has an equal number of 0’s and 1’s} D = {w|w has an equal number of occurrences of 01 and 10 substrings} Consider B: DFA must “remember” how many 0’s it has seen impossible with finite state. The others are exactly the same...
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.5
Negative Results Is there a DFA that accepts B = {0n 1n |n ≥ 0} C = {w|w has an equal number of 0’s and 1’s} D = {w|w has an equal number of occurrences of 01 and 10 substrings} Consider B: DFA must “remember” how many 0’s it has seen impossible with finite state. The others are exactly the same... Question: Is this a proof? Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.5
Negative Results Is there a DFA that accepts B = {0n 1n |n ≥ 0} C = {w|w has an equal number of 0’s and 1’s} D = {w|w has an equal number of occurrences of 01 and 10 substrings} Consider B: DFA must “remember” how many 0’s it has seen impossible with finite state. The others are exactly the same... Question: Is this a proof? Answer: No, D is regular!??? (see problem set 1) Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.5
Pumping Lemma We will show that all regular languages have a special property. Suppose L is regular.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.6
Pumping Lemma We will show that all regular languages have a special property. Suppose L is regular. If a string in L is longer than a certain critical length (the pumping length),
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.6
Pumping Lemma We will show that all regular languages have a special property. Suppose L is regular. If a string in L is longer than a certain critical length (the pumping length), then it can be “pumped” to a longer string by repeating an internal substring any number of times.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.6
Pumping Lemma We will show that all regular languages have a special property. Suppose L is regular. If a string in L is longer than a certain critical length (the pumping length), then it can be “pumped” to a longer string by repeating an internal substring any number of times. The longer string must be in L too.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.6
Pumping Lemma We will show that all regular languages have a special property. Suppose L is regular. If a string in L is longer than a certain critical length (the pumping length), then it can be “pumped” to a longer string by repeating an internal substring any number of times. The longer string must be in L too. This is a powerful technique for showing that a language is not regular. Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.6
Pumping Lemma Theorem: If L is a regular language, then there is an > 0 (the pumping length), where if s is any string in L of length |s| > , then s may be divided into three pieces s = xyz such that
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.7
Pumping Lemma Theorem: If L is a regular language, then there is an > 0 (the pumping length), where if s is any string in L of length |s| > , then s may be divided into three pieces s = xyz such that for every i > 0, xy i z ∈ L, |y| > 0, and |xy| ≤ .
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.7
Pumping Lemma Theorem: If L is a regular language, then there is an > 0 (the pumping length), where if s is any string in L of length |s| > , then s may be divided into three pieces s = xyz such that for every i > 0, xy i z ∈ L, |y| > 0, and |xy| ≤ . Remarks: Without the second condition, the theorem would be trivial.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.7
Pumping Lemma Theorem: If L is a regular language, then there is an > 0 (the pumping length), where if s is any string in L of length |s| > , then s may be divided into three pieces s = xyz such that for every i > 0, xy i z ∈ L, |y| > 0, and |xy| ≤ . Remarks: Without the second condition, the theorem would be trivial. The third condition is technical and sometimes useful. Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.7
Pumping Lemma – Proof Let M = (Q, Σ, δ, q1 , F ) be a DFA that accepts L. Let be |Q|, the number of states of M .
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.8
Pumping Lemma – Proof Let M = (Q, Σ, δ, q1 , F ) be a DFA that accepts L. Let be |Q|, the number of states of M . If s ∈ L has length at least , consider the sequence of states M goes through as it reads s:
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.8
Pumping Lemma – Proof Let M = (Q, Σ, δ, q1 , F ) be a DFA that accepts L. Let be |Q|, the number of states of M . If s ∈ L has length at least , consider the sequence of states M goes through as it reads s: s1
s2
s3
s4
s5
s6
...
sn
↑
↑
↑
↑
↑
↑
↑
↑
↑
q1
q20
q9
q17
q12
q13
q9
q2
q5 ∈ F
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.8
Pumping Lemma – Proof Let M = (Q, Σ, δ, q1 , F ) be a DFA that accepts L. Let be |Q|, the number of states of M . If s ∈ L has length at least , consider the sequence of states M goes through as it reads s: s1
s2
s3
s4
s5
s6
...
sn
↑
↑
↑
↑
↑
↑
↑
↑
↑
q1
q20
q9
q17
q12
q13
q9
q2
q5 ∈ F
Since the sequence of states is of length |s| + 1 > , and there are only different states in Q, at least one state is repeated (by the pigeonhole principle). Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.8
Pumping Lemma – Proof (cont.) Write down s = xyz x q1
z
q9 y
q5
By inspection, M accepts xy k z for every k ≥ 0.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.9
Pumping Lemma – Proof (cont.) Write down s = xyz x q1
z
q9 y
q5
By inspection, M accepts xy k z for every k ≥ 0. |y| > 0 because the state (q9 in figure) is repeated.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.9
Pumping Lemma – Proof (cont.) Write down s = xyz x q1
z
q9 y
q5
By inspection, M accepts xy k z for every k ≥ 0. |y| > 0 because the state (q9 in figure) is repeated. To ensure that |xy| ≤ , pick first state repetition, which must occure no later than + 1 states in sequence. Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.9
An Application Theorem: The language B = {0n 1n |n > 0} is not regular. Proof: By contradiction. Suppose B is regular, accepted by DFA M . Let be the pumping length. Consider the string s = 0 1 .
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.10
An Application Theorem: The language B = {0n 1n |n > 0} is not regular. Proof: By contradiction. Suppose B is regular, accepted by DFA M . Let be the pumping length. Consider the string s = 0 1 . By pumping lemma s = xyz, where xy k z ∈ B for every k.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.10
An Application Theorem: The language B = {0n 1n |n > 0} is not regular. Proof: By contradiction. Suppose B is regular, accepted by DFA M . Let be the pumping length. Consider the string s = 0 1 . By pumping lemma s = xyz, where xy k z ∈ B for every k. If y is all 0, then xy k z has too many 0’s.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.10
An Application Theorem: The language B = {0n 1n |n > 0} is not regular. Proof: By contradiction. Suppose B is regular, accepted by DFA M . Let be the pumping length. Consider the string s = 0 1 . By pumping lemma s = xyz, where xy k z ∈ B for every k. If y is all 0, then xy k z has too many 0’s. If y is all 1, then xy k z has too many 1’s.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.10
An Application Theorem: The language B = {0n 1n |n > 0} is not regular. Proof: By contradiction. Suppose B is regular, accepted by DFA M . Let be the pumping length. Consider the string s = 0 1 . By pumping lemma s = xyz, where xy k z ∈ B for every k. If y is all 0, then xy k z has too many 0’s. If y is all 1, then xy k z has too many 1’s. If y is mixed, then xy k z is not of right form. Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
♣ – p.10
Another Application Theorem: The language C = {w|w has an equal number of 0’s and 1’s} is not regular. Proof: By contradiction. Suppose C is regular, accepted by DFA M . Let be the pumping length. Consider the string s = 0 1 .
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.11
Another Application Theorem: The language C = {w|w has an equal number of 0’s and 1’s} is not regular. Proof: By contradiction. Suppose C is regular, accepted by DFA M . Let be the pumping length. Consider the string s = 0 1 . By pumping lemma s = xyz, where xy k z ∈ C for every k.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.11
Another Application Theorem: The language C = {w|w has an equal number of 0’s and 1’s} is not regular. Proof: By contradiction. Suppose C is regular, accepted by DFA M . Let be the pumping length. Consider the string s = 0 1 . By pumping lemma s = xyz, where xy k z ∈ C for every k. If y is all 0, then xy k z has too many 0’s.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.11
Another Application Theorem: The language C = {w|w has an equal number of 0’s and 1’s} is not regular. Proof: By contradiction. Suppose C is regular, accepted by DFA M . Let be the pumping length. Consider the string s = 0 1 . By pumping lemma s = xyz, where xy k z ∈ C for every k. If y is all 0, then xy k z has too many 0’s. If y is all 1, then xy k z has too many 1’s.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.11
Another Application Theorem: The language C = {w|w has an equal number of 0’s and 1’s} is not regular. Proof: By contradiction. Suppose C is regular, accepted by DFA M . Let be the pumping length. Consider the string s = 0 1 . By pumping lemma s = xyz, where xy k z ∈ C for every k. If y is all 0, then xy k z has too many 0’s. If y is all 1, then xy k z has too many 1’s. If y is mixed, then since |xy| ≤ , y must be all 0’s, contradiction. ♣ Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.11
Context Switch
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.12
Algorithmic Questions for NDAs Q.: Given an NDA, N , and a string s, is s ∈ L(N )? Answer: Construct the DFA equivalent to N and run it on w.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.13
Algorithmic Questions for NDAs Q.: Given an NDA, N , and a string s, is s ∈ L(N )? Answer: Construct the DFA equivalent to N and run it on w. Q.: Is L(N ) = ∅? Answer: This is a reachability question in graphs: Is there a path in the states’ graph of N from the start state to some accepting state. There are simple, efficient algorithms for this task.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.13
More Algorithmic Questions for NDAs Q.: Is L(N ) = Σ∗ ? Answer: Check if L(N ) = ∅.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.14
More Algorithmic Questions for NDAs Q.: Is L(N ) = Σ∗ ? Answer: Check if L(N ) = ∅. Q.: Given N1 and N2 , is L(N1 ) ⊆ L(N2 )? Answer: Check if L(N2 ) ∩ L(N1 ) = ∅.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.14
More Algorithmic Questions for NDAs Q.: Is L(N ) = Σ∗ ? Answer: Check if L(N ) = ∅. Q.: Given N1 and N2 , is L(N1 ) ⊆ L(N2 )? Answer: Check if L(N2 ) ∩ L(N1 ) = ∅. Q.: Given N1 and N2 , is L(N1 ) = L(N2 )? Answer: Check if L(N1 ) ⊆ L(N2 ) and L(N2 ) ⊆ L(N1 ).
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.14
More Algorithmic Questions for NDAs Q.: Is L(N ) = Σ∗ ? Answer: Check if L(N ) = ∅. Q.: Given N1 and N2 , is L(N1 ) ⊆ L(N2 )? Answer: Check if L(N2 ) ∩ L(N1 ) = ∅. Q.: Given N1 and N2 , is L(N1 ) = L(N2 )? Answer: Check if L(N1 ) ⊆ L(N2 ) and L(N2 ) ⊆ L(N1 ). In the future, we will see that for stronger models of computations, many of these problems cannot be solved by any algorithm. Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.14
Another, More Radical Context Switch So far we saw
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.15
Another, More Radical Context Switch So far we saw finite automata,
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.15
Another, More Radical Context Switch So far we saw finite automata, regular languages,
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.15
Another, More Radical Context Switch So far we saw finite automata, regular languages, regular expressions,
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.15
Another, More Radical Context Switch So far we saw finite automata, regular languages, regular expressions, pumping lemma for regular languages.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.15
Another, More Radical Context Switch So far we saw finite automata, regular languages, regular expressions, pumping lemma for regular languages. We now introduce stronger machines and languages with more expressive power:
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.15
Another, More Radical Context Switch So far we saw finite automata, regular languages, regular expressions, pumping lemma for regular languages. We now introduce stronger machines and languages with more expressive power: pushdown automata,
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.15
Another, More Radical Context Switch So far we saw finite automata, regular languages, regular expressions, pumping lemma for regular languages. We now introduce stronger machines and languages with more expressive power: pushdown automata, context-free languages,
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.15
Another, More Radical Context Switch So far we saw finite automata, regular languages, regular expressions, pumping lemma for regular languages. We now introduce stronger machines and languages with more expressive power: pushdown automata, context-free languages, context-free grammars,
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.15
Another, More Radical Context Switch So far we saw finite automata, regular languages, regular expressions, pumping lemma for regular languages. We now introduce stronger machines and languages with more expressive power: pushdown automata, context-free languages, context-free grammars, pumping lemma for context-free languages. Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.15
Context-Free Grammars This is an example of a context free grammer, G1 : A → 0A1 A→B B→#
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.16
Context-Free Grammars This is an example of a context free grammer, G1 : A → 0A1 A→B B→# Terminology: Each line is a substitution rule or production. Each rule has the form: symbol → string. The left-hand symbol is a variable (usually upper-case).
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.16
Context-Free Grammars This is an example of a context free grammer, G1 : A → 0A1 A→B B→# Terminology: Each line is a substitution rule or production. Each rule has the form: symbol → string. The left-hand symbol is a variable (usually upper-case). A string consists of variables and terminals.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.16
Context-Free Grammars This is an example of a context free grammer, G1 : A → 0A1 A→B B→# Terminology: Each line is a substitution rule or production. Each rule has the form: symbol → string. The left-hand symbol is a variable (usually upper-case). A string consists of variables and terminals. One variable is the start variable. Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.16
Rules for Generating Strings Write down the start variable (lhs of top rule).
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.17
Rules for Generating Strings Write down the start variable (lhs of top rule). Pick a variable written down in current string and a derivation that starts with that variable.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.17
Rules for Generating Strings Write down the start variable (lhs of top rule). Pick a variable written down in current string and a derivation that starts with that variable. Replace that variable with right-hand side of that derivation.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.17
Rules for Generating Strings Write down the start variable (lhs of top rule). Pick a variable written down in current string and a derivation that starts with that variable. Replace that variable with right-hand side of that derivation. Repeat until no variables remain.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.17
Rules for Generating Strings Write down the start variable (lhs of top rule). Pick a variable written down in current string and a derivation that starts with that variable. Replace that variable with right-hand side of that derivation. Repeat until no variables remain. Return final string (concatenation of terminals).
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.17
Example Grammar G1 : A → 0A1 A→B B→#
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.18
Example Grammar G1 : A → 0A1 A→B B→# Derivation with G1 : A ⇒ ⇒ ⇒ ⇒ ⇒
0A1 00A11 000A111 000B111 000#111
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.18
A Parse Tree A A A B 0
0
0
#
1
1
1
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.19
A Parse Tree A A A B 0
0
0
#
1
1
1
Question: What strings can be generated in this way from the grammar G1 ?
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.19
A Parse Tree A A A B 0
0
0
#
1
1
1
Question: What strings can be generated in this way from the grammar G1 ? Answer: Exactly those of the form 0n #1n (n ≥ 0).
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.19
Context-Free Languages The language generated in this way is the language of the grammar.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.20
Context-Free Languages The language generated in this way is the language of the grammar. For example, L(G1 ) is {0n #1n |n ≥ 0}.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.20
Context-Free Languages The language generated in this way is the language of the grammar. For example, L(G1 ) is {0n #1n |n ≥ 0}. Any language generated by a context-free grammar is called a context-free language.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.20
A Useful Abbreviation Rules with same variable on left hand side A → 0A1 A → B are written as:
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.21
A Useful Abbreviation Rules with same variable on left hand side A → 0A1 A → B are written as: A → 0A1 | B
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.21
English-like Sentences A grammar G2 to describe a few English sentences: < SENTENCE > → < NOUN-PHRASE >< VERB > < NOUN-PHRASE > → < ARTICLE >< NOUN > < NOUN > → boy | girl | flower < ARTICLE > → a | the < VERB > → touches | likes | sees
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.22
Deriving English-like Sentences A specific derivation in G2 : < SENTENCE > ⇒ < NOUN-PHRASE >< VERB > ⇒ < ARTICLE >< NOUN >< VERB > ⇒ a < NOUN >< VERB > ⇒ a boy < VERB > ⇒ a boy sees
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.23
Deriving English-like Sentences A specific derivation in G2 : < SENTENCE > ⇒ < NOUN-PHRASE >< VERB > ⇒ < ARTICLE >< NOUN >< VERB > ⇒ a < NOUN >< VERB > ⇒ a boy < VERB > ⇒ a boy sees
More strings in G2 : a flower sees the girl touches Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.23
Derivation and Parse Tree < SENTENCE >
⇒
< NOUN-PHRASE >< VERB >
⇒
< ARTICLE >< NOUN >< VERB >
⇒
a < NOUN >< VERB >
⇒
a boy < VERB >
⇒
a boy sees
SENTENCE
NOUN-PHRASE
VERB
ARTICLE
NOUN
a
boy
sees
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.24
Formal Definitions A context-free grammar is a 4-tuple (V, Σ, R, S) where V is a finite set of variables,
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.25
Formal Definitions A context-free grammar is a 4-tuple (V, Σ, R, S) where V is a finite set of variables, Σ is a finite set of terminals,
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.25
Formal Definitions A context-free grammar is a 4-tuple (V, Σ, R, S) where V is a finite set of variables, Σ is a finite set of terminals, R is a finite set of rules: each rule is a variable and a finite string of variables and terminals.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.25
Formal Definitions A context-free grammar is a 4-tuple (V, Σ, R, S) where V is a finite set of variables, Σ is a finite set of terminals, R is a finite set of rules: each rule is a variable and a finite string of variables and terminals. S is the start symbol.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.25
Formal Definitions If u and v are strings of variables and terminals,
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.26
Formal Definitions If u and v are strings of variables and terminals, and A → w is a rule of the grammar, then
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.26
Formal Definitions If u and v are strings of variables and terminals, and A → w is a rule of the grammar, then we say uAv yields uwv, written uAv ⇒ uwv.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.26
Formal Definitions If u and v are strings of variables and terminals, and A → w is a rule of the grammar, then we say uAv yields uwv, written uAv ⇒ uwv. ∗
We write u ⇒ v if u = v or u ⇒ u1 ⇒ . . . ⇒ uk ⇒ v. for some sequence u1 , u2 , . . . , uk .
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.26
Formal Definitions If u and v are strings of variables and terminals, and A → w is a rule of the grammar, then we say uAv yields uwv, written uAv ⇒ uwv. ∗
We write u ⇒ v if u = v or u ⇒ u1 ⇒ . . . ⇒ uk ⇒ v. for some sequence u1 , u2 , . . . , uk . Definition: The language of the grammar is ∗ w|S⇒w . Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.26
Example Consider G4 = (V, {a, b} , R, S). R (Rules): S → aSb | SS | ε .
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.27
Example Consider G4 = (V, {a, b} , R, S). R (Rules): S → aSb | SS | ε . Some words in the language: aabb, aababb.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.27
Example Consider G4 = (V, {a, b} , R, S). R (Rules): S → aSb | SS | ε . Some words in the language: aabb, aababb. Q.: But what is this language?
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.27
Example Consider G4 = (V, {a, b} , R, S). R (Rules): S → aSb | SS | ε . Some words in the language: aabb, aababb. Q.: But what is this language? Hint: Think of parentheses.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.27
Arythmetic Example Consider (V, Σ, R, E) where V = {E, T, F } Σ = {a, +, ×, (, )} E → E+T |T Rules: T → T × F | F F → (E) | a
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.28
Arythmetic Example Consider (V, Σ, R, E) where V = {E, T, F } Σ = {a, +, ×, (, )} E → E+T |T Rules: T → T × F | F F → (E) | a Strings generated by the grammer: a + a × a and (a + a) × a.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.28
Arythmetic Example Consider (V, Σ, R, E) where V = {E, T, F } Σ = {a, +, ×, (, )} E → E+T |T Rules: T → T × F | F F → (E) | a Strings generated by the grammer: a + a × a and (a + a) × a. What is the language of this grammer? Hint: arithmetic expressions.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.28
Arythmetic Example Consider (V, Σ, R, E) where V = {E, T, F } Σ = {a, +, ×, (, )} E → E+T |T Rules: T → T × F | F F → (E) | a Strings generated by the grammer: a + a × a and (a + a) × a. What is the language of this grammer? Hint: arithmetic expressions. E = expression, T = term, F = factor. Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.28
Parse Tree for a + a × a E → E+T |T T → T ×F |F F → (E) | a
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.29
Parse Tree for a + a × a E → E+T |T T → T ×F |F F → (E) | a E
E
T
T
T
F
F
a
+
a
F X
a
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.29
Parse Tree for (a + a) × a E → E+T |T T → T ×F |F F → (E) | a
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.30
Parse Tree for (a + a) × a E
T
E → E+T |T T → T ×F |F F → (E) | a
T F E E
(
T
T
F
F
a
+
a
F )
X
a
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.30
Designing Context-Free Grammars No recipe in general, but few rules-of-thumb If CFG is the union of several CFGs, rename variables (not terminals) so they are disjoint, and add new rule S → S1 | S2 | . . . | Si .
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.31
Designing Context-Free Grammars No recipe in general, but few rules-of-thumb If CFG is the union of several CFGs, rename variables (not terminals) so they are disjoint, and add new rule S → S1 | S2 | . . . | Si . To construct CFG for a regular language, “follow” a DFA for the language. For initial state q0 , make R0 the start variable. For state transition δ(qi , a) = qj add rule Ri → aRj to grammer. For each final state qf , add rule Rf → ε to grammer.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.31
Designing Context-Free Grammars No recipe in general, but few rules-of-thumb If CFG is the union of several CFGs, rename variables (not terminals) so they are disjoint, and add new rule S → S1 | S2 | . . . | Si . To construct CFG for a regular language, “follow” a DFA for the language. For initial state q0 , make R0 the start variable. For state transition δ(qi , a) = qj add rule Ri → aRj to grammer. For each final state qf , add rule Rf → ε to grammer. For languages with linked substrings (like {0n #1n |n ≥ 0} ), a rule of form R → uRv may be helpful, forcing desired relation between substrings. Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.31
Closure Properties Regular languages are closed under
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.32
Closure Properties Regular languages are closed under union
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.32
Closure Properties Regular languages are closed under union concatenation
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.32
Closure Properties Regular languages are closed under union concatenation star
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.32
Closure Properties Regular languages are closed under union concatenation star Context-Free Languages are closed under
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.32
Closure Properties Regular languages are closed under union concatenation star Context-Free Languages are closed under union : S → S1 | S2
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.32
Closure Properties Regular languages are closed under union concatenation star Context-Free Languages are closed under union : S → S1 | S2 concatenation S → S1 S2
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.32
Closure Properties Regular languages are closed under union concatenation star Context-Free Languages are closed under union : S → S1 | S2 concatenation S → S1 S2 star S → ε | SS
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.32
More Closure Properties Regular languages are also closed under
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.33
More Closure Properties Regular languages are also closed under complement (reverse accept/non-accept states of DFA)
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.33
More Closure Properties Regular languages are also closed under complement (reverse accept/non-accept states of DFA) intersection L1 ∩ L2 = L1 ∪ L2 .
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.33
More Closure Properties Regular languages are also closed under complement (reverse accept/non-accept states of DFA) intersection L1 ∩ L2 = L1 ∪ L2 . What about complement and intersection of context-free languages?
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.33
More Closure Properties Regular languages are also closed under complement (reverse accept/non-accept states of DFA) intersection L1 ∩ L2 = L1 ∪ L2 . What about complement and intersection of context-free languages? Not clear . . .
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.33
Ambiguity Grammar: E → E+E | E×E | (E) | a E E E a
E +
a
E X
a
E E E a
E +
a
E X
a
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.34
Ambiguity We say that a string w is derived ambiguously from grammer G if w has two or more parse trees that generate it from G.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.35
Ambiguity We say that a string w is derived ambiguously from grammer G if w has two or more parse trees that generate it from G. Ambiguity is usually not only a syntactic notion but also a semantic one, implying multiple meanings for the same string.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.35
Ambiguity We say that a string w is derived ambiguously from grammer G if w has two or more parse trees that generate it from G. Ambiguity is usually not only a syntactic notion but also a semantic one, implying multiple meanings for the same string. It is sometime possible to eliminate ambiguity by finding a different context free grammer generating the same language. This is true for the grammer above, which can be replaced by unambiguous grammer from slide (14x2).
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.35
Ambiguity We say that a string w is derived ambiguously from grammer G if w has two or more parse trees that generate it from G. Ambiguity is usually not only a syntactic notion but also a semantic one, implying multiple meanings for the same string. It is sometime possible to eliminate ambiguity by finding a different context free grammer generating the same language. This is true for the grammer above, which can be replaced by unambiguous grammer from slide (14x2). Some languages (e.g. {1i 2j 3k | i = j or j = k} are inherentrly ambigous. Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.35
Chomsky Normal Form A simplified, canonical form of context free grammers. Every rule has the form A → BC A → a S → ε where S is the start symbol, A, B and C are any variable, except B and C not the start symbol, and A can be the start symbol. Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.36
Theorem Theorem: Any context-free language is generated by a context-free grammar in Chomsky normal form. Basic idea: Add new start symbol S0 .
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.37
Theorem Theorem: Any context-free language is generated by a context-free grammar in Chomsky normal form. Basic idea: Add new start symbol S0 . Eliminate all ε rules of the form A → ε.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.37
Theorem Theorem: Any context-free language is generated by a context-free grammar in Chomsky normal form. Basic idea: Add new start symbol S0 . Eliminate all ε rules of the form A → ε. Eliminate all “unit” rules of the form A → B.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.37
Theorem Theorem: Any context-free language is generated by a context-free grammar in Chomsky normal form. Basic idea: Add new start symbol S0 . Eliminate all ε rules of the form A → ε. Eliminate all “unit” rules of the form A → B. Patch up rules so that grammar generates the same language.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.37
Theorem Theorem: Any context-free language is generated by a context-free grammar in Chomsky normal form. Basic idea: Add new start symbol S0 . Eliminate all ε rules of the form A → ε. Eliminate all “unit” rules of the form A → B. Patch up rules so that grammar generates the same language. Convert remaining long rules to proper form.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.37
Proof Add new start symbol S0 and rule S0 → S. Guarantees that new start symbol does not appear on right-hand-side of a rule.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.38
Proof Eliminating ε rules. Repeat: remove some A → ε.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.39
Proof Eliminating ε rules. Repeat: remove some A → ε. for each R → uAv, add rule R → uv.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.39
Proof Eliminating ε rules. Repeat: remove some A → ε. for each R → uAv, add rule R → uv. and so on: for R → uAvAw add R → uvAw, R → uAvw, and R → uvw.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.39
Proof Eliminating ε rules. Repeat: remove some A → ε. for each R → uAv, add rule R → uv. and so on: for R → uAvAw add R → uvAw, R → uAvw, and R → uvw. for R → A add R → ε, except if R → ε has already been removed.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.39
Proof Eliminating ε rules. Repeat: remove some A → ε. for each R → uAv, add rule R → uv. and so on: for R → uAvAw add R → uvAw, R → uAvw, and R → uvw. for R → A add R → ε, except if R → ε has already been removed. until all ε-rules not involving the original start variable have been removed.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.39
Proof Eliminate unit rules. Repeat: remove some A → B.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.40
Proof Eliminate unit rules. Repeat: remove some A → B. for each B → u, add rule A → u, unless this is previously removed unit rule. (u is a string of variables and terminals.)
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.40
Proof Eliminate unit rules. Repeat: remove some A → B. for each B → u, add rule A → u, unless this is previously removed unit rule. (u is a string of variables and terminals.) until all unit rules have been removed.
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.40
Proof Finally, convert long rules. To replace each A → u1 u2 . . . uk (for k ≥ 3), introduce new non-terminals N1 , N2 , . . . , Nk−1 and rules
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.41
Proof Finally, convert long rules. To replace each A → u1 u2 . . . uk (for k ≥ 3), introduce new non-terminals N1 , N2 , . . . , Nk−1 and rules A → u1 N1 N1 → u2 N2 .. . Nk−3 → uk−2 Nk−2 Nk−2 → uk−1 uk Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
♠ – p.41
Conversion Example Initial Grammar: S → ASA | aB A → B|S B → b|ε (1) Add new start state: S0 S A B
→ → → →
S ASA | aB B|S b|ε
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.42
Conversion Example (2) S0 S A B
→ → → →
S ASA | aB B|S b|ε
(2) Remove ε-rule B → ε: S0 S A B
→ → → →
S ASA | aB | a B|S|ε b|ε
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.43
Conversion Example (3) S0 S A B
→ → → →
S ASA | aB | a B|S|ε b
(3) Remove ε-rule A → ε: S0 S A B
→ → → →
S ASA | aB | a | AS | SA | S B|S|ε b
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.44
Conversion Example (4) S0 S A B
→ → → →
S ASA | aB | a | AS | SA | S B|S b
(4) Remove unit rule S → S S0 S A B
→ → → →
S ASA | aB | a | AS | SA | S B|S b
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.45
Conversion Example (5) S0 S A B
→ → → →
S ASA | aB | a | AS | SA B|S b
(5) Remove unit rule S0 → S: S0 S A B
→ → → →
S | ASA | aB | a | AS | SA ASA | aB | a | AS | SA B|S b
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.46
Conversion Example (6) S0 S A B
→ → → →
ASA | aB | a | AS | SA ASA | aB | a | AS | SA B|S b
(6) Remove unit rule A → B: S0 S A B
→ → → →
ASA | aB | a | AS | SA ASA | aB | a | AS | SA B|S|b b
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.47
Conversion Example (7) S0 S A B
→ → → →
ASA | aB | a | AS | SA ASA | aB | a | AS | SA S|b b
Remove unit rule A → S: S0 S A B
→ → → →
ASA | aB | a | AS | SA ASA | aB | a | AS | SA S | b | ASA | aB | a | AS | SA b
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
– p.48
Conversion Example (8) S0 S A B
→ → → →
ASA | aB | a | AS | SA ASA | aB | a | AS | SA b | ASA | aB | a | AS | SA b
(8) Final simplification – treat long rules: S0 S A A1 U B
→ → → → → →
AA1 | U B | a | SA | AS AA1 | U B | a | SA | AS b | AA1 | U B | a | SA | AS SA a b
Slides modified by Benny Chor, based on original slides by Maurice Herlihy, Brown University.
√ – p.49
View more...
Comments
