Computer Science 456/656
Automata and Formal Languages
Fall 2005
Goals
Regular Languages

Revised September 6, 2005

Definitions.

The student should understand the three formal definitions of regular language, and why they are equivalent.

Intuitive Understanding of Regularity.

The student should intuitively understand that a language is regular if and only if the recognition problem for that language can be decided by a finite state automaton, or, equivalently, by any machine with finite memory.

The student should be comfortable with the fact that a machine with finite memory can decide the recognition problem for an infinite language.

Non-Determinism.

The student should have clear understanding of what it means for a machine, possibly a non-deterministic machine, to accept a language.

Minimizing Automata.

The student should know the definition of minimal automaton, and should know that the minimal deterministic finite automaton is unique up to relabeling the states.

The student should be able to minimize a given deterministic finite-state automaton.

Equivalence of Deterministic and Non-deterministic Automata.

The student should be able to construct a minimal DFA equivalent to a given simple NFA.

Regular Expressions

The student should know the definition of a regular expression over a given alphabet is, and what what the definition of the language described by a given regular expression is.

The student should know that a language is regular if and only if it can be described by a regular expression.

The student should be able to give a regular expression for a regular language.

The student should be able to design an NFA which accepts the language described by a given regular expression.

Sets of Natural Numbers.

The student should know what it means for a set of natural numbers to be regular, and should be able to determine whether a given set of natural numbers is regular.

Classic Languages and Sets.

The student should know which well-known languages are regular. Examples of well-known languages include:

1. The set of all binary numerals for a well-known set of integers.
2. The set of all decimal numerals for a well-known set of integers.
3. The set of all unary numerals for a well-known set of integers.
4. The set of regular expressions over a given alphabet.
5. The set of strings satisfying a finite set of local conditions.
6. A finite set of strings.
7. A co-finite set of strings.

The student should know which well-known sets of integers are regular. Examples of well-known sets of natural numbers include:

1. All even numbers.
2. All multiples of 17.
3. All powers of 7.
4. All primes.
5. Finite sets of integers.