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

- Coverage
- Through Pumping Lemma basic concepts
- No coverage of Grammars and Context Free Languages
- Primarily on material covered in lecture and notes, through Chapter 10 of the text, as noted below, plus Appendix A.
- Homeworks
- Approximately equal weight on each covered chapter, except less weight on the math Appendix and very little the pumping lemma chapter.
- 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
- Contradiction
- Induction - Not on exam 1 - may be on exam 2
- Pigeonhole Principle
- A = B for sets A and B
- Chapter 1: Why?
- No topics
- 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 Σ:**un**countably infinite - Operations (aka Functions) on
**Languages**: - Union
- Intersection
- Complement (Universe: usually Σ* )
- Concatenation
- Kleene Star and Plus: L
^{*}and L^{+} - Reverse: L
^{R} - 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
- Chapter 4: Computation
- Not on exam 1: Skip it for now
- 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
- 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]
- Chapter 7: Regular Grammars
- Not on Exam 1
- 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
- Chapter 9: Not on exam
- Chapter 10: Summary - as relevant

ITEC 420 Home Page -- Dr. Okie's Home Page, | What's My Grade? |