Computer Science 3331A/B Chapter Notes - Chapter 1: Partial Function, Formal Language, Cardinality
22 Jan 2020
School
Department
Course
Professor
Document Summary
Automaton- construct that possesses all the indispensable features of a digital computer. Accepts input, produces output, temporary storage, make decisions transiforming input into output. Formal language- consists of set of symbols and rules of formation by which symbosl can be combined into entities called sentences". Set of all sentences permitted by rules of formation. Powerset- set of all subsets of a set s. denoted by s^s. If s = {a,b,c} then 2^s = {empty, {a},{b},{c},{ab}{ac}{bc}{abc}} Equivalance relation- if satisfies reflexivity, symmetry, and transitivity. * denotes set of strings obtained byt concatenating zero or more symbols from . Is finite because there will be a finite number of characters, * and + will always be infinite. Language is a set of concatenated alphabet like above. Star closure of a language: l* = l0 or l1 or l2 or ln.
