31-10-2012, 05:12 PM
Formal Languages and Automata Theory - Regular Expressions and Finite Automata
Formal Languages.pdf (Size: 139.52 KB / Downloads: 204)
Why should you read this?
If you already know what a regular expression is and what a finite state machine (or a
finite automaton) is, then you probably also know that given a regular expression many
times it is very difficult to directly construct the corresponding finite automaton. This
is because there are two intermediate steps that you should go through before you can
come up with the finite automaton. This note will explain to you what these two steps
are. Most of the proofs given here are constructive in nature, i.e. they will help you to
come up with an algorithm. All the proofs are to a large extent informal, and the aim
has been to explain the basic underlying concepts. If you understand these, then you
should be able to come up with more formal proofs on your own.
A word about notation
There is a slight deviation in notation from what has been presented to you during the
lecture, and what you are going to read here. Be assured that both the notations mean
the same thing.
First of all, we use the term finite automaton (FA). In many books this is also called
a finite state machine. Both are exactly the same. In the script and in the lecture this
was referred to as the Endlicher Automat.
Regular Expressions and the Corresponding Languages
Here we will see how new languages can be constructed from existing ones by using
three simple operations–union (denoted by
of a single string which is either of length one, or is the null string–and then apply
any combination of the three operators, then the resulting languages are called regular
languages. Such languages can be described by explicit formulas called regular expressions
and they consist of the three operations mentioned, i.e. union, concatenation,
and the closure operation.
Deterministic Finite Automata
In this section we will discuss about simple machines which will be used for recognizing
the languages introduced in the last section. This means that given a language L,
we will design a machine ML, which on given any string s as input,
We will see that regular languages can be characterized in terms of the “memory”
required to recognize them. We will restrict ourselves to machines which will read
any string presented to them in a single pass from left to right. This will help us to
clarify what information needs to be “remembered” during the process of recognizing
a language, and allows a classification of languages on the basis of how much needs to
be remembered at each step in order to recognize the language. Regular languages are
the simplest in this respect, there are other more “difficult” languages which we will
not consider here.