ITEC 420: Exam 1 topics - Fall 2019

1. 2019 Sep 28 11:19:53 AM: Added countability proofs to 2.5 and the word "alphabets" in 3.1
2. 2019 Sep 25 09:20:01 PM: Updated for fall 2019

1. Coverage: Material from text, powerpoints, lecture, homeworks
1. Text:
• Appendix A: Mainly sections A.2, A.3, A.4. From A.1: reading and meaning the symbols ∃ and ∀. Section A.6: Proof by contradiction, definition of countably and uncountably infinite, proof of countably infinite
• Chapter 2: Languages
• Chapter 5 - Sections 5.1-5.4: Regular Languages and D/ND FSM
2. Approximately equal weight on each covered chapter. (May change after exam is written)
3. Regular Expressions and Regular Grammars: Not on exam 1 (except that they are another way to define regular languages)


2. Appendix A: Math
1. Sets:
• Set builder notation: Specification and reading in English
• Cardinality
• Countable sets, Countably and uncountably infinite sets
• Operations on sets
• Power Set: definition, formation, size
2. Cartesian Product (aka Cross Product) - Creates set of tuples
• Ordered pairs and ordered tuples


3. Relation: any subset of Cross Product
4. Functions:
• A subset of cross product of the domain and range that has the function property
• Domain, range, mapping
• One-to-one, onto, bijection


5. Proofs
• Proof by Contradiction
• Proof that a set is countably infinite


3. Chapter 2: Languages and Strings
1. Alphabet: Σ - Finite set of symbols. (Can be empty, but we mostly ignore empty alphabets)
2. String: finite sequence of symbols, length, (|w|)
3. ε
4. Σ*


5. Operations on Strings:
• Concatenation
• Replication
• Reverse - (Know meaning, not formal definition)
6. Substrings, prefixes, suffixes


7. Languages - Introduction:
• Definition - What is a language!
• Notation for defining languages (ie set builder)
• Describing languages in English
• Empty language vs language containing empty string
• Lexicographic order (as defined in text)
• Σ* - Set of all strings formed from Σ
• Σ* is countably infinite
• Number of languages over nonempty Σ: uncountably infinite


8. Operations (aka Functions) on Languages:
• Union
• Intersection
• Complement (Universe: usually Σ* )


• Concatenation
• Kleene Star and Plus: L^* and L⁺
• Reverse: L^R
9. Scope in set builder notation
10. ZOM vs OOM, followed by, etc


4. Chapter 5: Deterministic Finite State Machines [and Regular Languages]
1. FSM Diagram: States and transitions, initial, finals
2. Formal definition: Five tuple - M = (K, Σ, δ, s, A)
3. Transition function: K x Σ x K
• Exactly one transition out of each state for each input symbol


4. Accept and reject a string
5. A machine accepts (ie recognizes) a language (ie L(M))


6. Computation: Formal and informal defintion
• Configuration and yields
• Initial, accepting, rejecting configuration


7. Regular Language: Give definition (ie accepted by FSM)


5. Chapter 5: Nondeterministic Finite State Machines [and Regular Languages]
1. DFSM: transition function: one transition out per input symbol
2. NDFSM
• transitions out per input symbol: 0, 1, 2, ...
• epsilon transitions
• New formal definition: Δ relation vs δ function and Δ defined on ε
• New definition of accepts: Some/any path
• Dead states no longer needed (but allowed)
• Typical operations: eg choices
• Interpretation (ie how to process):
1. Choose correct path (ie oracle knows path to follow to recognize)
2. Search tree (depth first or breadth first?)
3. Follow all paths at once (ie use fingers)


3. DFSM = NDFSM:
• a DFSM is obviously a NDFSM
• convert NDFSM to DFSM
• Use sets of ND states as states for deterministic machine
• eps of a state, applied after transition


4. Be able to analyze a N/DFSM
5. Be able to create a N/DFSM for a particular task


6. What does this mean: DFSM = NDFSM = RE = RG = RL
7. Acronyms: FSM, DFSM, NFSM, DFA, NFA, FA

1. Appendix A: Math
• Proofs:
• Induction
• Pigeonhole Principle
• A = B for sets A and B
• Set Closed under an operation: what it means and examples
• Closure of a set under an operation: what it is and how to find
2. Chapter 6: Regular Expressions - Not on exam 1.
• Except that they are another way of defining regular languages
• Will be on exam 2


• Basics:
• 8 forms: 3 base case, 5 recursive, 2 shorthands, parens
• L(α) - language described or defined by RE α
• Common operations and idioms
• Precedence
• Be able to analyze a RE
• Be able to create a RE to generate a specified language
• Kleene's Theorem
• RE to NDFSM
• NDFSM to RE: standard form and ripping states
• Simplifying RE [Not on exam 1]


3. Chapter 7: Regular Grammars - Not on exam 1
• Except that they are another way of defining regular languages


4. Chapter 1: Why? - Not on exam 1
5. Chapter 3: The Big Picture? --- not on exam 1
• Decision Problems: Given a language L and a string w, is w in L?
• Language hierarchy: recognition that it exists
6. Chapter 4: Computation - Not on exam 1
7. Chapter 8: Regular and Nonregular Languages - Not on exam 1
• Closure properties of Regular Languages - and why:
• Union
• Intersection
• Complement (Careful)
• Pumping Lemma: not on exam 1
8. Chapter 9: Not on exam 1
9. Chapter 10: Summary - not on exam 1