Transcript Slide 1

Proof of the Day:
Let P= {(b, acbb), (aac, a), (b, ca)}.
1. Prove that P has a match.
2. Find Q which is P encoded in binary.
3.What match of Q corresponds to the
match of P you found for Question #1?
4. Compute |P| and |Q| as defined on the
assignment.
1
Announcements
Assignment #1 is due on Wed. at the
beginning of class.
On Question 2(a), you do not have to find
a closed formula for the coefficients of
the resulting polynomial. Just argue
that they are constants say c0, c1, c2, …
then solve in terms of the ci’s.
2
Regular
Languages
http://eloquentjavascript.net/img/xkcd_regular_expressions.png
3
Σ* = set of all strings over alphabet Σ
Language over Σ – any subset of Σ*
Examples: Σ = {0, 1}
L1 = { w  Σ* : w has an even number of 0’s}
L2 = { w  Σ* : w is the binary representation of a
prime number with no leading zeroes}
L3 = Σ*
L4 = { } = Φ
L5 = { ε }
4
Operations on Languages:
1. Complement of L defined over Σ =
= { w  Σ* : w is not in L }
2. Concatenation of Languages L1 ۰ L2 = L1 L2 =
{w= x۰y for some x  L1 and y L2}
3. Kleene star of L, L* = { w= w1 w2 w3 … wk for
some k ≥ 0 and w1, w2, w3, … ,wk are all in L}
4. L+ = L ۰L*
(Concatenate together one or more strings
from L.)
5
Regular Languages over Alphabet Σ:
[Basis] 1. Φ and {σ} for each σ  Σ are
regular languages.
[Inductive step] If L1 and L2 are regular
languages, then so are:
2. L1 ۰ L2 ,
3. L1 ⋃ L2 , and
4. L1 *.
6
Regular expressions over Σ:
[Basis] 1. Φ and σ for each σ  Σ are
regular expressions.
[Inductive step] If α and β are regular
expressions, then so are:
2. ( αβ)
3. (α⋃β)
4. α*
and
Note: Regular expressions
are strings over
Σ ⋃ { (, ), Φ,⋃, * }
for some alphabet Σ.
7
Precedence of Operators
Exponents
Multiplication
Addition
highest
⇩
lowest
Kleene star
Concatenation
Union
8
Assume that p, q, and r are in
.
1. Note that the number of pairs (p,q) with
p + q = k is k+1. Use this to prove that
the number of 3-tuples (p, q, r) with
p+q+r = k is
1 + 2 + 3 + … + k + k+1 = (k+1) (k+2)/2.
2. Prove that the set S=
{ (p,q,r) : p, q, and r are in
}
is countable.
9