### ITEC 420: Exam 1 topics - Fall 2017

1. 2017 Oct 06 12:00:02 PM: Updated for Fall 17

1. Coverage
1. Through Pumping Lemma basic concepts
2. No coverage of Grammars and Context Free Languages
3. Primarily on material covered in lecture and notes, through Chapter 10 of the text, as noted below, plus Appendix A.
4. Homeworks
5. Approximately equal weight on each covered chapter, except less weight on the math Appendix and very little the pumping lemma chapter.

2. Appendix A: Math
• 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
• Cartesian Product (aka Cross Product)
• Ordered pairs and ordered tuples
• Relation: any subset of Cross Product
• Functions: a subset of cross product of the domain and range that has the function property
• domain, range, mapping, one-to-one, onto, bijection
• Set Closed under an operation: what it means and examples
• Closure of a set under an operation: what it is and how to find
• Proofs
• Induction - Not on exam 1 - may be on exam 2
• Pigeonhole Principle
• A = B for sets A and B

3. Chapter 1: Why?
• No topics

4. Chapter 2: Languages and Strings
• Alphabet: Σ (Finite set of symbols. Can be empty, but ignored)
• String: finite sequence of symbols, length, (|w|)
• ε
• Σ*
• Operations on Strings:
• Concatenation
• Replication
• Reverse - (Know meaning, not formal definition)
• Substrings, prefixes, suffixes

• Languages - Introduction:
• Definition
• Notation for defining languages
• Empty language vs language containing empty string
• Lexicographic order
• Σ* is countably infinite
• Number of languages over nonempty Σ: uncountably infinite

• Operations (aka Functions) on Languages:
• Union
• Intersection
• Complement (Universe: usually Σ* )
• Concatenation
• Kleene Star and Plus: L* and L+
• Reverse: LR

5. Chapter 3: The Big Picture? --- Will not be 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: Skip it for now

7. Chapter 5: Finite State Machines [and Regular Languages]
• FSM Diagram: States and transitions, initial, finals
• Formal definition: Five tuple - (K, Σ, δ, s, A)
• Transition function: K x Σ x K
• One transition out of each state for each input symbol
• Accept and reject a string
• A machines accepts (ie recognizes) a language
• Computation: Formal and informal defintion
• Configuration and yields

• Give definition of a Regular Language

• DFSM: one transition out per input symbol
• NDFSM
• transitions out per input symbol: 0, 1, 2, ...
• epsilon transition
• New formal definition: Δ relation vs δ function, Δ defined on ε
• New definition of accepts
• Dead states no longer needed
• Typical operations: eg choices
• Search tree vs follow all paths
• DFSM = NDFSM:
• a DFSM is obviously a NDFSM
• convert NDFSM to DFSM
• eps of a state, applied after transition

• Be able to analyze a N/DFSM
• Be able to create a N/DFSM for a particular task

8. Chapter 6: Regular Expressions
• 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]

9. Chapter 7: Regular Grammars
• Not on Exam 1

10. Chapter 8: Regular and Nonregular Languages - Not on exam 1 (except for general concepts of Pumping Lemma)
• What does this mean: DFSM = NDFSM = RE = RL

• Not on exam 1: Closure properties of Regular Languages - and why:
• Union
• Intersection
• Complement (Careful)

• Number of languages and number of regular languages: Both countable

• Pumping Lemma: General concepts only

11. Chapter 9: Not on exam
12. Chapter 10: Summary - as relevant