2.5.6 Exercises for Section 2.5 * Exercise 2.5.1: Consider the following e-NFA.

a) Compute the e-closure of each state.

b) Give all the strings of length three or less accepted by the automaton.

c) Convert the automaton to a DFA.

Exercise 2.5.2: Repeat Exercise 2.5.1 for the following e-NFA:

Exercise 2.5.3: Design e-NFAs for the following languages. Try to use e-transitions to simplify your design.

a) The set of strings consisting of zero or more as followed by zero or more bs, followed by zero or more cs,

! b) The set of strings that consist of either 01 repeated one or more times or 010 repeated one or more times.

! c) The set of strings of Os and Is such that at least one of the last ten positions is a 1.

2.6 Summary of Chapter 2

f Deterministic Finite Automata: A DFA has a finite set of states and a finite set of input symbols. One state is designated the start state, and zero or more states are accepting states. A transition function determines how the state changes each time an input symbol is processed.

> Transition Diagrams: It is convenient to represent automata by a graph in which the nodes are the states, and arcs are labeled by input symbols, indicating the transitions of that automaton. The start state is designated by an arrow, and the accepting states by double circles.

f Language of an Autojiiaton: The automaton accepts stringH. A string is accepted if, starting in the start state, tlie transitions caused by processing the symbols of that string one-at-a-time lead to an accepting state. In terms of the transition diagram, a string is accepted if it is tlie label of a path from the start state to some accepting state.

f Nondeterministic Finite Automata: The NFA differs from the DFA in that the NFA can have any number of transitions (including zero) to next states from a given state on a given input symbol.

-f The Subset Construction: By treating sets of states of an NFA as states of a DFA, it is possible to convert any NFA to a DFA that accepts the same language,

-f e-Transitions: We can extend the NFA by allowing transitions on an empty input, i.e., no input symbol at all. These extended NFAs can be converted to DFAs accepting the same language.

♦ Text-Searching Applications: Nondeterministic finite automata are a useful way to represent a pattern matcher that scans a large body of text for one or more keywords. These automata arc either simulated directly in software or are first converted to a DFA, which is then simulated.

2.7 References for Chapter 2

The formal study of finite-state systems is generally regarded as originating with [2]. However, this work was based on a neural nets model of computing, rather than the finite automaton we know today. The conventional DFA was independently proposed, in several similar variations, by [1], [3], and [4], The nondeterministic finite automaton and the subset construction are from [5].

1. D. A. Huffman, The synthesis of sequential switching circuits, ,/. Franklin Inst. 257:3-4 (1954), pp. 161-190 and 275-303.

2. W, S. McCulloch and W, Pitts, A logical calculus of the ideas inmianent in nervious activity, Bull. Math. Biophysics 5 (1943), pp. 115-133.

3. G. H. Mealy, A method for synthesizing sequential circuits, Bell Sy.stem Technical Journal 34:5 (1955), pp. 1045-1079,

4. E. F. Moore, Gedanken experiments on sequential machines, in [6], pp. 129-153,

5. M. O. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Research and Development 3:2 (1959), pp. 115-125.

6. C. E. Shannon and J. McCarthy, Automata Studies, Princeton Univ. Press, 1956.

Chapter 3

Regular Expressions and Languages

We bogiii this chapter by introducing the notation called regular expressions. These expressions are another type of language-delining notation, which we sampled briefly in Section 1.1.2. Regular expressions also may be thought of as a programming language, in which we express some important applications, such as text-search applications or compiler components. Regular expressions are closely related to nondeterministic finite automata and can be thought of as a user-friendly alternative to the NFA notation for describing software components.

In this chapter, after defining regular expressions, we show that they axe capable of defining all and only the regular languages. We discuss the way that regular expressions are used in several software systems. Then, we examine the algebraic laws that apply to regular expressions. They have significant resemblance to the algebraic laws of arithmetic, yet there are also some important difference.4 between the algebras of regular expressions and arithmetic expressions.

3.1 Regular Expressions

Now, we switch our attention from machine-like descriptions of languages - deterministic and nondeterministic finite automata - to an algebraic description: the regular expression. We shall find that regular expressions can define exactly the same languages that the various forms of automata describe: the regular languages. However, regular expressions offer something that automata do not: a declarative way to express the strings we want to accept. Thus, regular expressions serve as the input language for many systems that process strings. Examples include: