### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Theoretical Foundations CSCI 3236

GSU

GPA 3.52

### View Full Document

## 50

## 0

## Popular in Course

## Popular in ComputerScienence

This 97 page Class Notes was uploaded by Leonor Kulas on Monday October 12, 2015. The Class Notes belongs to CSCI 3236 at Georgia Southern University taught by Lixin Li in Fall. Since its upload, it has received 50 views. For similar materials see /class/221981/csci-3236-georgia-southern-university in ComputerScienence at Georgia Southern University.

## Popular in ComputerScienence

## Reviews for Theoretical Foundations

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/12/15

Cardinality Cardinality a measurement to compare the size of sets 0 lntuitively the cardinality of a set is the number of elements in the set 0 This informal de nition is suf cient when dealing with nite sets 0 What about in nite sets Cardinality 3 0 Two sets X andY have the same cardinality if there is a total onetoone function from X ontoY card X 2 card Y o The cardinality of a set X is less than or equal to the cardinality of a setY if there is a total onetoone function from X intoY card X 3 card Y Schr der Bernstein Theorem If card X S card Y an bard Y S card X then card X 2 card Y Countable ancl uncountable Sets 0 The cardinality of a nite set is the number of elements in the set 0 A set has the same cardinality as the set of natural numbers is countably in nite or denumerable The term countable refers to sets that are either nite or denumerable A set that is not countable is uncountable N Example N O is countany in nite fn n de nes a total and onetoone function from N onto NO Example 2 The set of odd natural number is countany in nite fn 2n de nes a total and onetoone function from N onto the oddnaturaInumber set A set is countany in nite if its elements can be put in a onetoone correspondence with the natural numbers Example 3 o The set of integers Z is countany in nite Example 3 NxN ordered pairs of natural numbers has the same cardinality as N Some Theorems 0 The union of two countable sets is countable o The Cartesian product of two countable sets is countable The set of nite subsets of a countable set is countable The set of nitelength sequences consisting of elements of a countable set is countable Uncountable sets A set is uncountable if it is impossible to sequentially list its members Cantor s diagonalization o Cantor s Diagonalization is a general proof technique for demonstrating that a set is not countable 0 Use Cantor s diagonalization method show that the set of all total functions from N to N is an uncountable setTo prove using contradiction Step 1 Assume that the set is countable and therefore its members can be exhaustively listed Step 2 Producing a member of the set that cannot occur anywhere in the listing by diagonalization Step 3 Achieving a contradiction Proof Assume that the set of total functions from N to N is denumerableThen there is a sequence f ff that contains all the functions Consider the total function f N gtN defined by fnfnn1 By de nition fn i fi i for every iThusf is not in the sequence f ff This is a contradiction since the sequence was assumed to contain all the total functions Thus our assumption that the set of total functions from N to N is countable must be false and we conclude that the function is uncountable Example Show that the power set PN the set of subsets of N is uncountable Proof Assume that PN is countable Then there is a sequence N0 NI N2 which is an exhaustive listing of the subsets of N Define a subset D of N as follows For every nature number j j E D if and only iijNj Since D is a subset of N and N0 NI N2 listing of all subsets of N DNi for some i Is the number i in the set D By definition of D 139 E D ifcmd only ifi E N But since DNi this becomes 139 E D if and only ifi E D which is a contradiction is an exhaustive Thus our assumption that PN is countable must be false and we conclude that PN is uncountable Recursive definitions Manymost of the sets of interest in formal language and automata theory contain an in nite number of elements o It is necessary to develop techniques to describegeneraterecognize the elements that belong to an in nite set 0 A recursive de nition of a set X speci es a method for constructing the elements of the set Recursive Definitions 0 Two components 0 The basis 39 Consisting of a finite set of elements that are explicitly designated as members of X 0 A set of operations 39 Construct new elements of the set from previously defined members 0 Essence to de ne complicated processes or structures in terms of simpler instances of the same process or structure Recursive Definition A recursive de nition of N is constructed using the successor function s Basis 0 e N Recursive step If n e N then Sm e N Closure n e N only if it can be obtained from 0 by a nite number of applications of the operation 5 Recursive Definition 2 The sum of m and n I Basis If nO then mnm 2 Recursive step msnsmn 3 Closure m n k only if this equality can be obtained from m0m using nitely many applications of the recursive step The closure step is often omitted from a recursive de nition N Example Compute the sum of 3 and 2 recursively SSS0 SS0 SSSS0 S0 SSSSS0 0 SSSSS0 Mathematical Induction Veri cation of correctness of a property Pn concerning all n can be done as follows 0 Prove the case nNO is true that is PNo is true 0 Prove that the Pk is true implies Pk I is true for all k that is greater than or equal to N0 Example Prove ngt2 for n 2 4 21 Example 2 0 Proof that O12nnn12 holds for all natural numbers n Directed Graphs o A directed graph is a pair V E consisting of a nite set V and binary relation E on theV The elements fromV are called vertices or nodes of the graph and the elements from E are called edges or arcs of the graph 0 A path from vertex x to vertex y is a sequence of vertices x0 XI xn such that o xixi is an edge 0 X0 X Xn Y o n is called the length of the path 0 The indegree of a node x is the number of arcs with x as the head 0 The outdegree of a node x is the number of arcs with x as the tail Directed Graph V 21 b c d E aab baa bye bad Cab Cad daa dad A path from a to c is abc its length 2 Node Indegree Outdegree a 2 1 b 2 3 c 1 2 3 2 Graphs and Trees 0 Cycle A path begins and ends with the same node 0 Cyclic graph A graph with at least one cycle 0 Acyclic graph A graph with no cycles 0 Tree An acyclic graph in which each node is connected by a unique path from a rootA root has indegree zero and all other nodes have in degree one Trees vs Graphs Cyclic graph Acyclic graph Tree Tree Terminology 3 0 Parent Child 0 The parent of a node is the node linked above it o If node u is the parent of node v then v is the child of u 0 Except for the root no parent every node has exactly one parent U V O Tree Terminology l o Siblings 0 Two nodes that are children of the same parent 0 N Tree Terminology 0 Leaf External node 0 A node is a leaf if it has no children 0 N Tree Terminology 0 Internal node 0 A node is internal if it has one or more children 0 N Tree Terminology 0 Ancestor Descendent 0 An ancestor of a node is either the node s parent or any ancestor of the node s parent this is recursive 0 The root is an ancestor of all other nodes b u b 11 N Tree Terminology i Subtree 0 The subtree ofT rooted at node v is the tree consisting of all the descendents of v in T including v b V b N Tree Terminology r a 0 Minimal common ancestor o The minimal common ancestor of two nodes x and y is an ancestor of both and is the smallest ancestor that is it is a descendant of all other common ancestors Tree Terminology Depth of a node 0 The depth of a node v in T is the number of ancestors of v excluding v itself 0 More formally va is the root the depth ofv is 0 Otherwise the depth of v is one plus the depth of the parent of v lt depth of v 1 depth of v 3 1 Tree Terminology 3 0 Height or depth of a tree 0 The depth of a tree is the maximum depth of any of its leaves tree depth 3 1 J tree depth 2 0 tree depth O Tree Terminology Node x is LEFTOF node y Suppose now we label the order of all siblings in a tree and o x y are two nodes neither of which is an ancestor of the other 0 Let 2 be the minimal common ancestor of the nodes x and y and let 239 22 Zn be the children of z in their correct order 0 Then x is on the LEFTOF y if 0 x is in the subtree generated by Zi is in the subtree generated by zjand iltj Node 4 is LEFTOF node 12 Node 9 is LEFTOF node 11 Chapter 2 Languages 0 Strings and Languages 0 languages strings alphabets 0 Finite Speci cation of Languages 0 union concatenation Kleenstar Kleenplus Regular Sets and Expressions Strings and Languages 0 An alphabet is a nonempty finite set of symbols It is denoted 2 0 Z abcdefghijkmnopqrstuvwxyz A string is a finite sequence of elements from an alphabet 0 school vacation famiy are strings over 2 0 A language is a set of strings over an alphabet 0 Languages of interest do not consist of arbitrary sets of strings but rather of strings having specified forms 0 The acceptable forms define the syntax of the languages Examples 0 English language 0 Alphabet the set of words and punctuation symbols 0 Computer Language 0 Alphabet the set of keywords identifiers and other special symbols 0 Note Language of interest are not made up of arbitrary strings 0 Not all strings of English words are sentences 0 Not all strings of source code are legitimate computer programs 0 Languages consist of strings that satisfy syntax Definition 0 Let 2 be an alphabet 2 the set of strings over 2 is de ned recursively as fol lows null string string containing no elements I Basiszl E 2 2 Recursive step ifw E 2 and a E 2 then ma E 2 3 Closure w E 2 only if it can be obtained from A by a finite number of applications of the recursive step o For any nonempty alphabet 2 2 contains in nite many elements 0 IfZ a E The length of a string w is the number of elements in the string lengthw If 2 contains n elements there are nk strings of length k inZ Example 0 Let 2 1 b c The elements of include 2 include Length 011 Length 1 a b C Length 2 cm ab ac ba bb bc ca CC Cb Length 3 arm aab lac alba abb abc acct curb acc baa bab bac bba bbb bbc bca beb bcc can cab cm Cba ebb Cbc cw CCb CCC Language o A language is a subset of Z 3 Exanu e Z 6119 2 1 6119 aaabbabbaaa 0 Languages 1 aaaaab 1 abba baba aa ab aaaaaa Another Language Example Laquotbquotn20 A ab aabb aaaaabbbbb gteL cwbeL Definition 0 Let ulv E 2 The concatenation of u and v written uv is a binary operation onZ de ned as follows I Basis If Iengthv 0 then vl and uvu 2 Recursive step Let v be a string with Iengthvngt0Then vwa for some string w with length nl and a E Z and uvuwa gtllt String Operations W alaz an abba v 91192 mbm bbbaaa Conca rena ri on WV 2 611612 manle quot39bm abbabbbaaa Cenca raaning a s rring wiTh ifsalf wnzwwmw W 0 Example n abba2 abbaabba w 611612 an ababaaabbb Reverse wR 2 an 612611 bbbaaababa String Length 39 w 611612 an 0 Length M n 0 Examples abba 4 aa 2 2 a zl 9 Empty String 1 0 Empty string or null stringz 0 Observations Ill 2 0 1w 2 WA 2 w 1R 2 l labba abbal abba w0 A may 1 Subsu ng o Substring of string 0 a subsequence of consecutive characters String Substring g bab ab abbab abba ab ab b abbab bbab Prefix and Suffix abbab Pre xes Suf xes A abbab yv a bbab prefix ab bab suffix abb ab abba b abbab The Operation 2 the set of all possible strings from alphabet Z Z 2 ab 2 16119 aaabbabb aaa aab w CSCI 3236 o 7 Theoretical Foundations Instructor Dr Lixin Li Georgia Southern University Introduction 0 Syllabus Course Objective 0 Mathematical foundation of CS Theoretical Foundations yo Formal language theory 0 How are languages de ned 0 It provides the foundation for constructing and implementing highlevel computer programming languages 0 Theory of Computation 0 What can be computed by a computer 0 Is there any problem cannot be solved using computers 0 How complex of a particular problem is 0 Machine Automata theory 0 nite automata pushdown automataTuring machine 0 Set theory is fundamental to the above study Set Theory 0 Set element membership notations belong 6 does not belongg Set de nition 0 ExplicitX 23Y abcd 0 Implicit n nm2 for some natural number m 0 Set examples 0 Natural number N 0 2 34 0 empty set D Set Theory Subsets proper subset power set of a set 0 Subset Y Q X Every member on is also a member of X 0 Proper subset Y c X 39 Y E X but Y t X 0 Power set PX 39 The set of all subsets of X Example 0 Let X 2 3 List all the subsets of X and the power set of X 0 All the subset of X Z 1 2 3 12 23 31 123 0 The power set PX 25 1 2 3 12 23 31 123 Set Operations Union XUYZZEX0rzeY Intersection X YzzeXcmdzeY Difference X YZZEXandZ Y Complement 0 Let X be the subset of UThe complement ofX with respect to U is YU X DeMorgan s laws W f m Y W f u Y Example 30 Let X 0 I 2 3 andY 2 34 5 f and Y denote the complements of X andY with respect to N Explicitly de ne the sets described below a XUY e f b XmY f F c X Y g X vY d Y X h Em Cartesian Product XxYxyxeXcmder Example 0 Let X 2 3 andY a b List the following Cartesian product results aXgtltY b YgtltX c YgtltY d XgtltYgtltY Relations 0 A binary relation on X andY is a subset of Xgtlt Y 0 Example the ordering of the natural numbers can be used to generate a relation LT less than on the set N gtltN LT is a subset of Ngtlt N de ned by LTijiltjandijeN 0 An nary relation on X X X is a subset of XIXXZXgtltXH Special case n1 unary n2 binary n3 ternary Functions 0 Functions are speci c types of relations 0 A function from a set X to a setY is a mapping of elements ofX to elements on f X gtY fx y 0 Each element of X is mapped to at most one element on X domainY range 0 nvariable functions szlxszgtltXn gtY Special case n1 unary n2 binary n3 ternary N Total Functions o If for every member of X there is exactly one member on that is related to it then we call R a total function from X toY It satisfies the following two operations i For each x e X there is a y e Y such that x y e f ii1fxy1e f and xy2 e f then y1 y2 Exercisel Tota Functions 0 Is the relation LT a total function LT iJHi ltj and i39 E N o Is the relation RT a total function RT iji gtj and ij e N Exercise2 Tota Functions 0 Let X 2 3 and Ya b List all the possible total functions from X toY N Partial Functions o If R is a relation from domainA to range B and R has the property that for every member of X there is at most one member on that is related to it then we call R a partial function from X toY o A partial function satis es the following operation Ifxyle f and xy2e ftheny1y2 0 Example integer division function div from N x N to N Difference between Total Functions and Partial Functions 0 A total function will be de ned for all values in the domain 0 A partial function may be unde ned for some values in the domain Function Terminology 0 Let s consider properties we could apply to a partial function 0 Let F be a partial function from domain A to range B with the following properties total gt For every element a in A there is an element b in B such that Fa b onto N2 For every b in B there is some a in A such that Fa b onetoonegt3 For no b in B are there two elements a and a2 inA such that Fal b and FaZ b Terminology 0 Some functions might satisfy one or more of these properties but not all of them 0 A function that satisfies I is called total 0 A function that satisfies 2 is called onto F is a function from A onto B rather than A to B o A function that satisfies 3 is called oneto one since each item in the domain can only map to one item in the range Total Function Onto Function Total and Onto Function Total and Onetoone Function Total and Onto and OnetoOne 1 Functions Finite Speci cation of Languages Recursive Definition of Language 3 0 Finite language language with finite number of strings can be listed string by string 0 Some in nite languages can be de ned by a set of rules Example 0 The language L of strings over a b in which each string begins with a and has even length can be de ned by I m aa abeL 2 Recursive step If u e L then uaa uab uba ubb e L 3 Closure Every u e L is obtained from the basis by a nite number of applications of the recursive step Operations on Languages Union Let X andY be languages 0 Union XwYuueX0rueY 0 Example 61 ab aaaa U bb ab 61 ab bl aaaa Operations on Languages ConcaTenaTion Let X andY be languages 0 Concatenation XYuvueX and veY 0 Example 61 ab ba 9 aa 2 ah aaa abb abaa bab baaa Operations on Languages 39 Conca rena ring a language with itself Let X be a language 0 De nition X 0 Example ab3 ababab 6161a 6161 aba abb baa bab bba 191919 0 Special case X0 1 abbaaaa0 1 Operations on Languages Kleene Sfar39 Let X be a language 0 De nition XX0 UX1UX2 Xi 0 Example 1 611919 612919 gtxlt eta 6119 bba 9191919 616161 61611919 61191961 abbbb Operations on Languages KIeenePlus Let X be a language 0 De nition X XIUX2 SXquot i1 0 Example 61 bl 611919 aaabbbbabbbb 616161 61611919 61191961 abbbb Example 2 a b l 0 Lo the language that consists of all strings formed by a and b 0 L0 abgtIlt LI the language that consists of all strings that end with aa 0 LI abaa 0 L2 the language that consists of all strings that begin with aa 0 L2 aaabgt lt L3 the language that consists of all strings that begin with aa or end with aa 0 L3 L2 U LI aaabgtlt U abaa 0 note for priority gt concatenation gt U 0 L4 the language that consists of all strings contain the substring aa 0 L4 abaaabgtlt 0 L5 the language that consists of all evenlength strings 0 L5 aa bb ab bagtlt 0 L6 the language that consists of all oddlength strings 0 L6 abgtlt L5 abgtlt aa bb ab bagtlt 0 or L6 abL5 ab aa bb ab bagtlt Regular Sets and Expressions 9 Regular Sets Languages 0 Let E be an alphabetThe regular sets or languages over 2 are de ned recursiver as follows 0 Basis Q A and a for every a 62 are regular sets over 2 0 Recursive step Let X and Y be regular sets over 2 The sets XUY XY and X are regular sets over 2 0 ClosureAny regular set can be obtained from the basis by applying a nite number of steps of the recursive step Example Show that L1b 1 bb1 is a regular language Consider all steps 1 b are regular by Basis 1b1 b is regular as concatenation of regular languages b1b 1 is regular as concatenation of regular languages 1Ub1 b is regular as the union of regular languages 1 b is regular as Kleene closure of regular language 1b 1 bb1 is regular as concatenation of regular languages All nite languages are regular In nite languages may be not regular N Examples of Regular Languages o L a bbbabgtIlt is regular over a b L is the language consisting of all strings containing the string bb o The language consisting of all strings that begin and end with a and contain at least one b is regular over a b o It is M aa bba ba Regular Expressions 1o PurposeWe want to use simpler NOTATIONS to represent regular anguagesthe basic idea is to remove and 0 Let 2 be an alphabet The regular expressions over 2 are defined recursiver as follows 0 Basis Q 7 and a an are regular expression over 2 0 Recursive step If u and v are regular expression over 2 so are the expressions uuv uv u 0 Closure Any regular expression can be obtained from the basis by applying a nite number of steps of the recursive step A regular set is corresponding to a regular expressionThey are equivalent 0 Every regular language can be written as a regular expression and vice versa In fact they are same since the constructions of them have the same 3step instructions basis recursive and closure Examples of Regular Expression 0 The regular language a can be denoted as a 3 k as 7 and a b as an a bgtlt as an o The languages L M in slide 33 can be denoted as 0 For L a bbbab llt gt anbban 0 For M aa bba ba gt aanbana o Operator Priority high to low Kleene Starlconcatenationlunion If u is a regular expression u uu u2uu and u uu quot Exercise for a given regular expression describe the regular set Zabc oanUcbcanUc the set consists of all string containing bc ababagtIlt the set of strings containing exactly 2 b s oeumeumum the set of strings containing at least 2 b s Exercise 2 Find a regular expression that represents the described set 2 ab o the strings that the number of b is even agt39ltbagt39ltbagt39ltgt lt U agt39lt agt39ltagt39ltbagt39ltbagt39ltilt how about odd number of b 61abagt39ltbagt39ltgt39ltabagt lt

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.