$msg = "";
$myaddress = "sacha" + "@" + "sachachua.com";
$page = "CS130.php";
$page_title = "C S 130";
$page_updated = "2004-11-21";
$http_equiv = "Content-Type";
$meta_content = "text/html; charset=utf-8";
$maintainer = "mailto:sacha@sachachua.com";
$home = "WelcomePage.php";
$index = "WikiIndex.php";
$style = <<
Textbook: Introduction to Automata Theory, Languages and Computation by John E. Hopcroft and Jeffrey D. Ullman (1979)
Course Outline:
The relation "=" = { (0,0), (1,1), (2,2), (3,3), ... } The relation ">" = { (1,0), (2,0), (3,0), (4,0), ... } The relation "<" = { (0,1), (0,2), (0,3), (0,4), ... }
The relation \modulo{}_3 = { (0,0), (0,3), (0,6), (0,9), ...
(1,1), (1,4), (1,7), (1,10), ... (2,2), (2,5), (2,8), (2,11), ... (3,0), (3,3), (3,6), (3,9), ... ... }
Definition: Suppose we let R be a relation on a set A. We will be writing aRb instead of (a,b) \elementof R to indicate a is related to b via the relation R.
Example 2: Consider A = {1, 2, 3} and a given relation R on A. a. R = {(1,3), (3,1), (2,2)} symmetric, not reflexive, not transitive b. R = {(1,1), (2,2), (3,3), (1,2)} not symmetric, reflexive, transitive
If R is symmetric and transitive, is R reflexive? Nope. Theorem: If a relation R on a set S is an equivalence relation, then R partitions S into disjoint non-empty equivalence classes, i.e. there exists S1, S2, S3, ... such that S = S1 U S2 U S3 U ... and for every i,j (i != j)
Ex. Let R = {(1,2),(2,2),(2,3)} be a relation on {1,2,3} => transitive closure of R: R^+ = {(1,2),(2,2),(2,3),(1,3),(2,3)} => symmetric-transitive closure of R: R^/ = {(1,2),(2,2),(2,3),(2,1),(3,2),(1,3),(3,1),(3,3),(1,1)}
E | = 0 | ||||
abc | = | aba | = | aaa | = 3 |
substring
prefix - initial substring (includes E) suffix - final substring (includes E) \sigma^* = set of all possible strings over \sigma {E, a, b, c, aa, ab, ac, ba, bb, bc, ...}
If the alphabet is {0,1}, then {0,1}* can be thought of as a generator. Given this operation, we can now define what a (formal) language is.
L recognizes
= { [e], a, b, aa, ab, ba, bb }
where n_i = # of i's in a string
= {a, ab, ba, aab, aba, baa, aabb, ... }
In fact the most interesting languages are those that are infinite.
xy = abbbab
Language: L_1 = {hope, fear}
L_2 = {ful, less}
L_1 L_2 = {hopeful, hopeless, fearful, fearless}
Definition of concatenation for languages:
Suppose we let L_1 and L_2 be languages over an alphabet [Sigma]. The concatenation of L_1 and L_2 is given as follows:
L_1 L_2 = cartesian product of L_1 and L_2
if k = 0
a^0 = [e]
x^0 = [e]
[Sigma^0] = {[e]}
L^0 = {[e]}
L_2 = {x element of {a,b}* x < 3}
L_3 = {x element of {a, b}* n_a(x) >= n_b(x)}
Concatenation operation
String: x = abb, y = bab
Exponential notation
Suppose we let
a [element of] [Sigma_1]
x [element of] [Sigma^*]
L [element of] [Sigma]
a^k = aaaaa...a a^k = k
x^k = xxxxx...x k terms x^k = k x
L^k = LLLLL...L k terms { [x_1][x_2][x_3]...[x_k] x_1 [element of] L, x_2 [element of] L, x_3 [element of] L, ... x_k [element of] L}
[sigma^k] = {x [element of] [Sigma^*] x = k }
Kleene closure of L
L^* = U(0, infinity, L^i}
Positive closure: L^+ = U(1, infinity, L^i}
Note: [L^*]L = L^+
Question: When will L^+ = L^* ? ( if L = {} or L contains [e] )
L is empty != L = {[e]}
{0,1}*{2}{0,1}*
example> Let [Sigma] be an alphabet, L be a language over [sigma].
Prove L^2 [subset=] L => L+ [subset=] L
This statement is equivalent to the statement
L^2 [subset=] L => U(1, infinity)L^n [subset=] L
n = 1 L^1 [s=] L
assume it's true for n = k
L^2 [s=] L => L^k [s=] L
L^2 [s=] L => LL^k [s=] LL
L^2 [s=] L => L^(k+1) [s=] L^2
Principles of Strong Math Induction
Suppose P(n) is a statement about n element of Z
To prove P(n) is true for n >= n_0, it is sufficient to show 2 things:
1) P(n) is true
2) for every k >= n_0, if P(n) is true for all n, n_0 <= n <= k, then P(k+1) is true.
Principles of Math Induction
Suppose P(n) is a statement involving n element of Z.
Then to prove P(n) is true if for each n >= n_0, it is
sufficient to show
Recursive Definitions
One of the most commonly used definitions is the recursive definition of the factorial. n! = { n = 0 ? 1 : n * (n - 1) }
Another one is the Fibonacci function f(n + 1) = f(n) + f(n - 1) where f(0) = f(1) = 1. f(4) = 5
Union(i = 1, n, A_i) = { A if n = 0, union(i = 1, n - 1, A_i) union A_n if n elementof Z+ }
axa elementof pal iv. No other string is in pal.
Parenthesized expressions
Let [Sigma] = { i, (, ), +, - } The language AE of fully parenthesized algebraic expressions involving operations +, - and the identifier i can be defined as: i. i elementof AE ii. For every string s1 and s2 in AE, (s1 + s2) elementof AE iii. For every string s1 and s2 in AE, (s1 - s2) elementof AE iv. Nothing else is in AE.Example 1
Suppose a language L, a subset of {0, 1}^*, is defined as follows:
Q = {q0, q1, q2, q3, q4, q5, q6} Sigma = {0, 1} delta =
\ 0 1 +------
q0 q3 q1 q1 q2 q6 q2 q4 q5 q3 q4 q5 q4 q4 q5 q5 q4 q6 q6 q2 q6
q_0 = q_0 F = { q4 }
simplified version q0, q1, q2
0 1 q0 q0 q1 q1 q2 q1 q2 q0 q1 **
Example 2:
Describe using regular expressions the FA below 0 1 q0 q1 q3 q1 q0 q2 q2 q2 q2 q3 q2 q4 final q4 q2 q3 initial, final
(00)*(11)*
0 1 q0 q4 q1 none, 110 q1 qX q2 1 q2 q0 q1 11 q3 q0 q1 final q4 qX qX final qX qX qX
q0 q1 q2 q1 q3 q3 final q2 q3 q4 q3 q3 q3 q4 q4 q2 q5 q1 q2 final
--- (a+b)*babaa
q1 q1 q2 initial q2 q3 q1 b q3 q1 q4 ba q4 q5 q1 bab q5 q6 q4 baba q6 q1 q2 final babaa
delta hat : Q x Sigma -> 2^Q
delta hat : Q x Sigma* -> 2^Q defined (recursively) as follows
delta hat(q, x) -> set of all reachable states from q via x
There exists a q elementof delta hat (q0, x) such that q elementof F
The string x elementof Sigma* is accepted by M iff delta hat(q0, x) intersection F is not the null set.
The language accepted (or recognized) by M is the set
L(M) = { x elementof Sigma* | x is accepted by M } |
Q is a finite set of states
Sigma is a finite alphabet of symbols q0 elementof Q is the initial state F subsetof Q is a set of final states delta is a transition function delta: Q x Sigma -> 2^Q (all the subsets of Q)
Conversion
NFA q0 0+1->q0 0->q1 1->q2 q1 0->q1 1->q3 q2 0->q4 1->q2 (q3) (q4)
DFA 0 1 q0 {q0,1} {q0,2} {q0,1} {q0,1} {q0,2,3} {q0,2} {q0,1,4} {q0,2} [{q0,2,3}] {q0,1,4} {q0,2} [{q0,1,4}] {q0,1} {q0,2,3}
0*(01)*
q0 ---0---> q1 ----1----> (q2)
U ^ | 0 +------0-------+ |
0 1 q0 q0,1 q3 q0,1 q0,1 q2,3 q2,3 q1 q3 q1 q0,1
NFA-epsilon
Example: Let r = 0*(01)*0*
Our idea will be the following. Suppose we have the following state diagram: p -0->q -e-> r -e-> s . To remove all epsilons, we simply copy the arrows to all of them, so p -0-> q
-0-> r -0-> s
A A,B,C,E D,E B C E C B D E D E
A {ABCE} {DE} {ABCE} {ABCE} {BDE} {DE} {E} {D} {BDE} {CE} {DE} {D} {DE} {CE} {B}
L(R) is the language generated by the regular expression R L(M) is the language recognized by DFA M
part 1: recall regular expression: built over simple expressions, 0, epsilon, a elementof Sigma operations Union (+), concatenation and Kleene closure
ii) assuming true for some ri exists Mi such that L(ri) = L(Mi) in particular: r1: ----[ () M1 (F, F') ]--epsilon-->(()) r2: ----[ () M2 (F, F') ]--epsilon-->(()) Show that
r1r2
r1 + r2 +----[ () M1 (F, F') ]--epsilon-->(()) --+
+----[ () M2 (F, F') ]--epsilon-->(())
r1* ---+---------------------+--epsilon-->(())
^ |
| +--[ () M1 (F, F') ]--+ |
or -----(())---[ () M1 (F, F') ]--+
+------------------------+
((0+1)*(10)+(00)*(11)*)*
(o)<------------------------------+
+-+--+-----+--1-->--0--------+---+ | ||||||||
^ | +--0--+ | +--1--+ | +--+--------+--+--------+--+ | |||||
^ | ^ |
| +--0--0--+ +--1--1--+ |
Let Rij^k = { x elementof Sigma* | deltahat(i,x) = j without "going through" a state labeled k+1 or more } |
Due January 10, 2002 Bonus +10 points if submitted on or before Options - Groups of at most 3
input file -> [ lexical analyzer ] -> output file containing tokens
For example:
int myNum = 7;
if (x == 1.4E-9) then
y = 2;
output:
www.math.grin.edu/~rebelsky/Courses/CS362/2001S/Project/project.01.html view this by tomorrow afternoon: www.math.admu.edu.ph/~jonjon/CS130/main.htm Submit before 12:00 nn tomorrow decisions: group, language Output:
example: ---()-"i"->()-"f"->()-blank->(())
J. Martin, _Introduction to Languages and the Theory of Computation (2nd Ed)_, McGraw-Hill Companies, Inc., 1997.
B. Mikolajczak (ed), Algebraic and Structural Automata Theory, _Annals of Discrete Mathematics_ 44, Elsevier Science Publishers B.V., 1985
The majority of the textbooks are available in the Cubao branch. Need this by Thursday.
Assignments will be given regularly; however, assignments will be checked randomly.
Dr. Mccluskey will arrive in January and handle the second half of CS130 for both classes.
When we're given, for example, some input: 5, 11 and the output: 16 What we've done between the input and the output is computing the sum.
In this sense we will be using 'computer' and 'algorithm' in the same sense as CS110 and CS101
Just as an overview, we will be discussing the following models for computation
Actually, the first part of the textbook deals with preliminaries only, and I will be assigning you to read Chapter 1 of the textbook. Submit by tomorrow a 3x5 index card with the following information: [Front] Chua, Sandra Jean V. Sacha 3 BS CS Philippine Science High School 12 August 1983 sachac@iname.com
[Back] Schedules Subject Room Time Days
---
The telephone of the Math department: 4266001 5680-83
include "include/footer.inc.php" ?>