Lesson 1 – Mathematical Preliminaries 1 – Set
CS154-03 Fall 2020
Math Preliminaries 1 -Set
Copyright By PowCoder代写 加微信 powcoder
GGeenerraal l Rules & Tips Assignment Big Pic • Check Canvas regularly
Assignments, announcements, lecture notes, etc. • Regular Office hour
General questions first • Appointment
Check Canvas for available slot(s)
…Previously
Definition Representation Size
Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
General RuRlueles &TTipisps Assignment Big Pic
Class protocols
• No sharing course materials
• No late homework question via Email
• Use the notations mentioned in lectures
• NO cheating!
Important Dates
• Aug. 31, Mon. Last day to drop without a W grade
• Dec. 9, Wed. Final Exam 12:15 – 14:30 PDT
…Previously
Definition Representation Size
Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
General Rules & Tips AsAssigignmeentnt Big Pic
• Practice quiz due on Sep. 6, Sun. 2 parts, 1 point if submit both
Part 2 is also for prerequisites check Always available (no late penalty)
• ~26 points from homework/midterm
~126 possible points, 93 and above for A, etc. Check under “Points Earned”
…Previously
Definition Representation Size
Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
General Rules & Tips Assignment B Four branches of Computation Theory
Complexity Computability Automata Formal Languages
What can be done in practice?
What can be done with computers?
…Previously
Definition Representation Size
Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously
InItnrtoroducctitoinon Definition Naming Examples
• A great role in mathematics and other sciences
In this course, we’ll use sets tremendously
• Created by (1845-1918)
German mathematician
Famous for the set theory
and infinities
Method to prove that the set
of real numbers is bigger than the set of natural numbers
Definition
Representation Size
Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously
Introduction DDeeffiinittioion n Naming Examples
• A set is a collection of objects (aka elements, members).
• Order does NOT matter
A collection of “ordered” objects is called “list” “list” and “set” are 2 different concepts
• All elements of a set must be “distinct” All objects in this universe are “distinct”
Repeated element(s) only count once Example: {3, 4, 1, 3, 2} = {3, 4, 1, 2}
Definition
Representation Size
Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously
Introduction Definition NNaamingg Examples
• Usually use English capital letters (A , B, C, etc.)
• Or Greek capital letters (Σ-sigma, Γ-gamma, etc.)
• Examples
A = {2, 7, 5}
V = {train , bike , airplane , bus}
The set of binary digits: Σ = {0, 1}
The set of natural numbers less than 6
and greater than 2: Γ = {3 , 4 , 5}
Definition
Representation Size
Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously
Introduction Definition Naming ExExaampleles s Is Σ a set?
• Σ = {ab , aabb, aaabbb}
Yes, the elements can be meaningless
• Σ = {5 , train , apple , California} Yes, the elements can be irrelevant
• Σ={1,2,3,4,5}
Yes, the elements can be ordered Is Σ a list?
Definition
Representation Size
Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously
Introduction Definition Naming ExExaampleles s Is Σ a set?
• Σ={1,2,2,3}
Yes, but 2 only count once (= {1, 2, 3})
• Σ={1,{2,3},2,3}
Yes, set is also an object
Definition
Representation Size
Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition
Ro Set Builder
Roster: enumerating members
• Put elements in a pair of curly-braces
• Each element separated with a comma
• Use … to bypass mentioning some elements
if the pattern of elements is obvious from the context.
• Example: The set of lowercase English letters: Σ = {a, b, c, …, z}
Representation
Size Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition
Roster Method VeVnennDiaggrarmam Set Builder
Putting all elements in a circle, ellipse, etc. • Example: A = {1, 5, 2}
• Named after (1834 – 1923)
• Useful for showing relationships/operations
Representation
Size Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition
Roster Method SeStetBuiildlderer {variable/pattern | description of the elements}
• Example1:A={x|1≤x≤5}
The set of all numbers between 1 and 5 (both included)
• Example2(pattern):A={an |1≤n≤3} ={a, aa, aaa}
• Use comma (,) for logical “AND”
Example 1 can also be written as A = { x | x ≥ 1, x ≤ 5 }
• For logical “OR”, explicitly put “OR” or “∨”
• OK to use colon (:) instead of the vertical bar |
Representation
Size Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation
CCaarrdinaaliltyity Empty Set Finite Set Infinite Set
The size of a set A is the number of its elements. • Denoted by |A|
• Example:ifA={1,3,2,6,5},|A|=?
• Example:ifA={1,3,1,6,5},|A|=?
4, since duplicate members should be eliminated
Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation
Cardinality EmEmptySSetet Finite Set Infinite Set Empty set is a set that has no member.
• Denotedby{}orφ. φ is pronounced “phi” Is {φ} empty set?
• Is A empty set?
A = { x | x < 1, x > 5 }
A = The set of “F-Students of this class”
Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation
Cardinality Empty Set Fi t Infinite Set
• A set is called finite if its size is a natural number. The set of natural numbers (not a finite set) is denoted
by N and starts from 0: N = {0, 1, 2, …}
• Example:LetB={a,b,c,…,z}.IsBafiniteset?
Yes, |B| = 26, which is a natural number • Is φ a finite set?
Yes, |φ| = 0
Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation
Cardinality Empty Set Finite Set InIfnifniniteSSetet
• A set is called infinite if we cannot express its size by a natural number.
• Examples
Integers: Z = {…, -2, -1, 0, 1, 2, …} Natural numbers: N = {0, 1, 2, …}
• Is A infinite set?
A = { x | x < 1 or x > 5} A = { x | x < 1, x > 5 }
Relations Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
MMeemberrsshihpip Subsets Complement Power Set
• element “∈” (belongs to) set
• Not membership: “∉” (not belong to)
• Example: Let C = {5 , train , apple} train ∈ C
bus ∉ C
• A set is known when its boundary is clearly defined What belongs to the set AND what does not
“not membership” is as important as “membership”
Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
Membership SSuubsetsts Complement Power Set
Set A is subset of B if every elements of A is also an element of B.
• This relationship is denoted by A ⊆ B
• Example:A={2,3},B={3,5,2},A⊆B
• IfA={2,3}andB={2,3},isA⊆B?
Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
Membership SSuubsetsts Complement Power Set
Proper Subset
• Set A is proper subset of B if all elements of A
belong to B, AND they are NOT equal.
• This relationship is denoted by A ⊂ B
• B is called superset of A
• Example:A={2,3},B={3,5,2},A⊂B
• IsitpossiblethatA⊂BANDB⊂A?
• IsitpossiblethatA⊆BANDB⊆A?
Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
Membership SSuubsetsts Complement Power Set
Equality of Two Sets
• Two sets A and B are equal if both have the same
• A=BiffA⊆BANDB⊆A
If A = B, then A ⊆ B AND B ⊆ A If A ⊆ B AND B ⊆ A, then A = B
• This relationship is denoted by A = B
Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
Membership Subsets CoCmomplemenetnt Power Set
Universal Set
• Universal set of a set is the set containing all
possible elements under consideration.
• It is denoted by “U”
• Rectangle in Venn diagram
• Example: A = {2, 6, 3}
U = {0, 1, 2, 3, 4, 5, 6} or U = {0, 1, 2, 3, …}, …
• Use in set builder
A = {x ∈ N | 1 ≤ x ≤ 5}, where N is the universal set of A
A3 6 51 2 4
Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
Membership Subsets CoCmomplemenetnt �Power Set • The complement of set A is denoted by A and is
defined as: A = {x | x ∈ U, x ∉ A} T o f i n d A� , w e n e e d U
• Example:A={3,5},U={1,2,3,4,5} A� = { 1 , 2 , 4 }
Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
Membership Subsets Complement PoPowerSSetet
• PowersetofAisthesetofallsubsetsofsetA
• It is denoted by 2A
• 2 ={x|x⊆A}
• Example:LetA={a,b},2A =?
2A is symbol and not an algebraic power A
2A ={φ,{a},{b},{a,b}}
• If set S has n elements (i.e. |S| = n), then its power
set has 2n elements. i.e. |2S| = 2|S|
Example: If A = {a, b, c}, |A| = 3 and |2A|= 8
Operations Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
OOppeerratiioonns s Properties (Proper) Subset Equal
Identities
Intersection Disjoint
*A� is a special case AB
Operations
Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
OOppeerratiioonns s Properties Identities
A ⋃ B = {x | x ∈ A ∨ x ∈ B}
• Intersection
A ⋂ B = {x | x ∈ A, x ∈ B}
What if A and B are disjointed?
A – B = {x | x ∈ A, x ∉ B}
What if A and B are disjointed? Complement: U – A
Operations
Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
Operations PrPoroperttieies s
• Commutative A⋃B=B⋃A A⋂B=B⋂A
• Associative
A ⋃ (B ⋃ C) = (A ⋃ B) ⋃ C A ⋂ (B ⋂ C) = (A ⋂ B) ⋂ C
• Distributive
A ⋃ (B ⋂ C) = (A ⋃ B) ⋂ (A ⋃ C) A ⋂ (B ⋃ C) = (A ⋂ B) ⋃ (A ⋂ C)
Identities
Operations
Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
Operations
Properties
IdIdeentittieies s
Identity Idempotent Complementation
Domination
A⋂A= A ⋃ A� =
A ⋂ A� = ( A� ) =
Complement
A⋂B = A�⋃B� A⋃B = A�⋂B�
Operations
Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
Relations Operations
In next class …
• Cartesian Products • Functions
Next class…
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
Relations Operations Next class…
DeDefifninitiioonns s Notations Exercises
• A set is a collection of objects (aka elements, members).
• A set is called finite if its size is a natural number.
• A set is called infinite if we cannot express its size by a
natural number.
• Universal set of a set is the set containing all possible
elements under consideration.
• The complement of set A is denoted by A� and is defined
as: A = {x | x ∈ U, x ∉ A}
• PowersetofAisthesetofallsubsetsofsetA
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
Relations Operations Next class…
Definitions
NNoottationns s
Concept / Relation
a is member of A
A is subset of Σ
Power set of A
Size of the power set of A
Universal set
c is not member of B
B is proper subset of Σ
Size of A (Cardinality of A)
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
Relations Operations Next class…
Definitions Notations ExExeerciisees s • Represent the following sets and its complement
by set builder �
(Natural numbers are the default numbers in this course, so we can eliminate it if the universal set is the natural numbers)
B = {0 , 3 , 6 , 9 , 12 , 15�, 18} = ?, B = ? L = {a, aa, aaa, …} = ?, L = ?
• Can {a, b} be a universal set of {a, b}?
• Let Z = {A-Students of this class}, give some
possible universal sets of Z
• IfS={1,2,3};2S =?
• If|A|=10,2|A| =?
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
Relations Operations Next class…
Definitions Notations ExExeerciisees s • What is the relationship between sets A and B in
the following situations: A⋃B=A
A–B=A A⋂B=A A–B=B–A A⋂B=B⋂A
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Math Preliminaries 1 -Set
…Previously Definition Representation Size
Relations Operations Next class…
References
• Linz, Peter, “An Introduction to Formal Languages and Automata, 5th ed.,” Jones & , LLC, Canada, 2012
• . Rosen, “Discrete Mathematics and Its Applications, 7th ed.,” McGraw Hill, , United States, 2012
• Sipser, Michael, “Introduction to the Theory of Computation, 3rd ed.,” CENGAGE Learning, United States, 2013 ISBN-13: 978-1133187790
CS 154: Formal Languages and Computability | Fall 2020 | Lesson 1
Lesson 14 – – In Action
CS154-03 Fall 2020
PDA 2 -In Action
InItnrtoroductitoinon Main Blocks Workflow Part1 • DFAs/NFAs have limited power because…
No memory! Can NOT store data
Use a “stack” to store data
Finite number of states
Deterministic (NPDA)
NO more than 1 (0 or 1) possible transition at a timeframe
Nondeterministic (NPDA)
Can have more than 1 possible transitions at a timeframe
…Previously
Workflow Part2 PDAs in Action NPDA
Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020
PDA 2 -In Action
Introduction MaMianinBlloccksks Workflow Part1 • Input tape
Same as DFA/NFA
Last in, first out (LIFO), “push” and “pop”
The special symbol ‘Z’ at the bottom
The “stack alphabet” and the “input tape alphabet” can be
totally different
• Control Unit
Similar to DFAs/NFAs, except for transition labels:
read , pop ; push
…Previously
Workflow Part2 PDAs in Action NPDA
Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020
PDA 2 -In Action
Introduction Main Blocks WoWrokrkffllowPParat1rt1
• Starting configuration
Timeframe 0, start from the left-most cell of input tape,
stack pointing at Z (empty), start from initial state
• Logic of transition
IF in state qi AND current symbol AND top of stack THEN consume AND pop AND push AND go to qj
• Use λ to relax read, pop, or push
“No condition” or “no action” for that condition/Operation This is the 3rd usage of λ, NOT λ-transition!
…Previously
Workflow Part2 PDAs in Action NPDA
Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020
PDA 2 -In Action
…Previously
NoNoTTranssitiotinon Halt Accept Reject
• If at least one condition does NOT meet, then no transition at that timeframe
• Example: suppose the PDA is in state qi, based on
the transition label, no transition if Current symbol is NOT a
Or the top of stack is NOT k
Or Current symbol is NOT a AND the top of stack is NOT k
qi a, k; b qj
Workflow Part2
PDAs in Action NPDA
Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020
PDA 2 -In Action
…Previously
No Transition Halltt Accept Reject
• Example: suppose the PDA is in state qi, and input symbol all consumed. The top the stack is y. Base on
the transition labels, does the PDA stop or go to qj? Go to qj!
Since there is possible transition! Stack
qi λ, y; b qj
Workflow Part2
PDAs in Action NPDA
Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020
PDA 2 -In Action
…Previously
No Transition Halltt Accept Reject
• A PDA halts iff there is no possible transition
h: NFA halts
z: There is zero transition
h ↔ z: h if and only if z
This means when the PDA halts, there may be symbols
that are not consumed yet
This also means, if all symbols are consumed, the PDA
may continue working, as long as there is a transition
Stack does NOT need to be empty
Workflow Part2
PDAs in Action NPDA
Next class… Appendix
CS 154: Formal Languages and Computability | Fall 2020
PDA 2 -In Action
…Previously
No Transition Halt AAccept t Reject
• PDA accepts a string iff it halts AND all symbols are
consumed AND the PDA is in an accepting state h: PDA halts
c: All input symbols are consumed
a: PDA accepts a string
f: PDA is in an accepting (final) state
( h ∧ c ∧ f ) ↔ a: h AND c AND f if and only if a
h and c may have different values so CANNOT simplify
However, h can be substituted with z (no transition)
Stack does NOT need to be empty – depends on problem
Workflow Part2
PDAs in Action NPDA
Next class… Appendix
CS 154: Formal