CS 322 / CSE 224 « AUTOMATA AND LANGUAGE THEORY
R 1 Rich, Elaine ( 2009 ) . Automata, Computability and Complexity. New Jersey : Pearson Prentice Hall
R 2 Cohen, Daniel I. A. ( 1991 ) . Introduction to Computer Theory . New York : John Wiley and Sons
R 3 Brookshear, J. Glenn . ( 1989 ) Theory of Computation, Formal languages, Automata, and Complexity . Redwood City,
California : The Benjamin / Cummings Publishing Company Inc. 1989
R 4 Kolman, Bernard ; Busby, Robert and Ross, Sharon Cutler ( 2000 ). Discrete Mathematical Structures 4th ed .
New Jersey : Prentice – Hall Inc.
Automata Theory, concept that describes
how machines mimic human behavior. The theory proposes that human
physical functions and behavior can be simulated by a mechanical or
computer-controlled device. Applications of automata theory have
included imitating human comprehension and reasoning skills using
computer programs, duplicating the function of muscles and tendons by
hydraulic systems or electric motors, and reproducing sensory organs by
electronic sensors such as smoke detectors.
The concept of automata, or manlike machines, has historically been
associated with any self-operating machine, such as watches or clockwork
songbirds driven by tiny springs and gears. But in the late 20th
century, the science of robotics (the development of computer-controlled
devices that move and manipulate objects) has replaced automata as it
relates to replicating motion based on human anatomy (see Robot).
Modern theories of automata currently focus on reproducing human
thought patterns and problem-solving abilities using artificial
intelligence and other advanced computer-science techniques.
BRIEF HISTORY
Automata date to ancient times. During the Han dynasty (3rd century BC), a mechanical orchestra was constructed for the Chinese Emperor. The 13th-century English philosopher and scientist Roger Bacon is credited with creating an artificial talking head, and in the 17th century French philosopher and mathematician René Descartes reportedly built a female automaton as a traveling companion.
In the 18th and 19th centuries, intricate machines were constructed
that imitated some human actions, such as limb movement, but these
devices were little more than sophisticated windup toys. Mimicry of human mental abilities
did not begin until the advent of electronics and mathematical logic
structures. In the mid-20th century, the British mathematician Alan Turing
designed a theoretical machine to process equations without human
direction. The machine (now known as a Turing machine), in concept
resembled an automatic typewriter that used symbols for math and logic
instead of letters. Turing intended the device to be used as a
“universal machine” that could be programmed to duplicate the function
of any other existing machine. Turing's machine was the theoretical
precursor to the modern digital computer.
In the 1940s and 1950s American researchers Warren McCulloch and Walter Pitts
at the Massachusetts Institute of Technology developed artificial
neurons, or neural networks, to theoretically bridge the structure of
the human brain and the still-to-be-invented modern computer. The human
brain has about 1 trillion nerve cells, or neurons, each of which is
connected to several other neurons. This allows neurons to transmit
information along different pathways, depending on the stimulation they
receive. McCulloch and Pitts theorized that this same mode of
information transmission, an interconnected network, might be reproduced
with electronic components. Artificial neural networks have been shown
to have the capacity to learn from their experiences and enhance their
computational performance.
In 1956 American social scientist and Nobel laureate Herbert Simon and American physicist and computer scientist Allan Newell at Carnegie Mellon University in Pennsylvania devised a program called Logic Theorist
that simulated human thinking on computers, although at first the
program was simply written on index cards due to the scarcity of
computers. Newell and Simon later created a modified version of the
program called the General Problem Solver
(GPS). The GPS was unique in that it was programmed to achieve a goal
and then find the means to reach that goal—as opposed to starting from a
problem or question and working toward an eventual solution. The GPS
process involved backward thinking, going from the final solution to the
present state. Using computers from the Rand Corporation to test GPS,
Simon and Newell found that in some cases GPS did act as if it were
capable of human reasoning. This was one of the first breakthroughs in
the computer-science field that would later be known as artificial intelligence.
The first artificial intelligence conference occurred at Dartmouth College
in New Hampshire in 1956. This conference inspired researchers to
undertake projects that emulated human behavior in the areas of
reasoning, language comprehension, and communications. In addition to
Newell and Simon, computer scientists and mathematicians Claude Shannon, Marvin Minsky, and John McCarthy
laid the groundwork for creating “thinking” machines from computers.
Contemporary fields of interest resulting from early artificial
intelligence research include expert systems, cellular automata, and
artificial life.
CHAPTER 1 * INTRODUCTION
The 20th
century has been filled with the most incredible shocks and surprises :
theory of relativity, Communist revolutions, psychoanalysis, nuclear
war, television, moon walks, genetic engineering, etc. As astounding as
any of these is the advent of the computer and its development from a
mere calculating device into what seems like a “thinking machine”. We
are not after the history computers but the we are concerned with the
theory of computers, which means that we form several abstract
mathematical models that will describe with varying degrees of accuracy
parts of computers and types of computers and similar machines.
There are separate courses that deal with circuits and switching
theory (computer logic) and with instruction sets and register
arrangements ( computer architecture) and with data structures and
algorithms, operating systems, compiler design and artificial
intelligence and etc. All these courses have theoretical component, but
they differ from our study in two aspects :
1. They deal with computers that already exist;
2. They are interested in how best to do things
The
history of computer theory is also interesting which was formed by
fortunate coincidences, involving seemingly unrelated branches of
intellectual endeavor. The most obvious component of computer theory is
the theory of mathematical logic.
Georg Cantor
( 1845 – 1918 ) invented the theory of sets, but at the same time he
had discovered some very uncomfortable paradoxes – he created things
that look like contradiction in what seemed to be rigorously proven
mathematical theorems. Some of his unusual findings could be tolerated (
such as that infinity comes in different sizes ) but some could not (
such as that some set is bigger is bigger than the universal set). This
left a cloud over mathematics that needed to be resolved.
David Hilbert
( 1862 – 1943 ) – wanted all of mathematics put on the same sound
footing as Euclidean geometry, which is characterized by precise
definitions, explicit axioms, and rigorous proofs. He believed that if
mathematics were put back on the Euclidean standard the cantor paradoxes
would go away. He was actually concerned with two ambitious projects :
1. To demonstrate that the new system was free of paradoxes;
2. To find methods that would guarantee to enable humans to construct proofs of all the
true statements in mathematics.
This type of complete, guaranteed, easy-to-follow set of instructions
is called algorithm. Hilbert hoped that algorithms or procedures could
be developed to solve whole classes of mathematical problems. Mathematical logicians
while trying to follow the suggestions of Hilbert and straighten out
the predicament left by Cantor, found that they were able to prove
mathematically that some of the desired algorithms cannot exists – not
only at this time, but they can never exist in the future.
Kurt Godel (
1906 – 1978 ) not only showed that there was no algorithm that could
guarantee to provide proofs for all the true statements in mathematics,
but he proved that not all the true statements even have a proof to be
found. Godel’s Incompleteness Theorem
implies that in a specific mathematical system either there are some
true statements without any possible proof or else there are some false
statements that can be “proven.”
Alonzo Church proposed the first general definition of an algorithm. Using his definition and together with
Stephen Cole Kleene, and independently Emil Post they were able to prove that there were problems that no algorithm could solve.
Alan Mathison Turing (1912-1954),
British mathematician, who did pioneering work in computer theory. He
was born in London and educated at Cambridge and Princeton universities.
In 1936, while he was still a graduate student, Turing published a
paper called “On Computable Numbers,” which introduced the concept of a
theoretical computing device now known as a Turing machine. The concept
of this machine, which could theoretically perform any mathematical
calculation, was important in the development of the digital computer.
Turing also extended his mathematical work to the study of artificial
intelligence and biological forms. He proposed a method called the
Turing test, to determine whether machines could have the ability to
think. During World War II (1939-1945), Turing worked as a cryptographer for the British Foreign Office. In 1951 Turing was named a Fellow of the Royal Society
and in 1952 he began to publish his work on the mathematical aspects of
pattern and form development in living organisms. He apparently
committed suicide in 1954 , probably in reaction to medical treatments
he was forced to receive in order to “cure” him of homosexuality.
Turing develop the concept of a theoretical “universal algorithm
machine.” Studying what was possible and what was not possible for such a
machine to do, he discovered that some task that we might have expected
this abstract omnipotent machine to be able to perform are impossible,
even for it. Turing’s model for a universal algorithm machine is
directly connected to the invention of the computer. In fact for a
completely different reason, Turing himself had an important part in the
construction of the first computer, which he based on his work in
abstract logic.
Sturgis McCulloch and Walter Pitts ( 1923 – 1969 ) constructed a mathematical model for the way
in which sensory receptor organs in animal behave. The model they
constructed for a “neural net” was a theoretical machine of the same
nature as the one Turing invented, but with certain limitations.
The
invention of the vacuum tube and the development in electronics enabled
engineers to build fully automatic electronic calculators. These
development fulfilled the age-old dream of Blaise Pascal (1623 – 1662), Gottfried
Wilhelm von Leibniz (1646 – 1716 ) an Charles Babbage (1792 – 1871), all of whom built mechanical calculating devices as powerful as their respective technologies would allow.
The First Generation Computers – built in the 1940’s :
1. The Computer Colossus at Bletchley, England ( Turing’ decoder )
2. The ABC Machine built by John Atanosoff in Iowa
3. Harvard Mark I built by Howard Aiken,
4. ENIAC, built by John Presper Eckert Jr. and John William Mauchly ( 1907–1980 )
at the University of Pennsylvania.
John von Neumann
(1903 – 1957 ) – developed the idea of a stored-program computer. The
idea of storing the program inside the computer and allowing the
computer to operate on ( and modify ) the program as well as the data
was a tremendous advance. This may also been conceived earlier by
Babbage and his co-worker Ada Augusta, Countess of Lovelace ( 1815 – 1853 ) but their technology was inadequate to explore this possibility.
Von Neumann’s
goal was to convert the electronic calculator into a real – life model
of one of the logician’s ideal universal algorithm machines, such as
those Turing had described. Along with the concept of programming a
computer came the question : What is the best language in which to write
programs.
Noam Chomsky
created the subject of mathematical models for the description of
languages to answer these questions. His theory grew to the point where
it began to shed light on the study of computer languages. The
formulation of mathematical logic became useful to linguistics , a
previously nonmathematical subject. Metaphorically, we could say that
the computer then took on linguistic abilities. It became a word
processor, a translator, and an interpreter of simple grammar, as well
as a compiler of computer languages. The software invented to interpret
programming languages was applied to human languages as well.
One point that will be made clear in the study is why computer
languages are easy for a computer to understand whereas human languages
are very difficult.
AUTOMATA THEORY
Automata
is defined as a system where energy, information and material is
transformed, transmitted and used for performing some function without
the direct participation of man . In theoretical computer science, automata theory is the study of abstract machines and problems they are able to solve. Automata theory is closely related to formal language theory as the automata are often classified by the class of formal languages they are able to recognize.
An automaton is a mathematical model for a finite state machine (FSM). A FSM is a machine that, given an input of symbols, "jumps" through a series of states according to a transition function (which can be expressed as a table). In the common "Mealy"
variety of FSMs, this transition function tells the automaton which
state to go to next given a current state and a current symbol.
The input is read
symbol by symbol, until it is consumed completely (think of it as a
tape with a word written on it, that is read by a reading head of the
automaton; the head moves forward over the tape, reading one symbol at a
time). Once the input is depleted, the automaton is said to have stopped.
Depending on the state in which the automaton stops, it's said that the automaton either accepts or rejects the input. If it landed in an accept state, then the automaton accepts the word. If, on the other hand, it lands on a reject state, the word is rejected. The set of all the words accepted by an automaton is called the language accepted by the automaton.
Note, however, that, in general, an automaton need not have a finite number of states, or even a countable number of states. Thus, for example, the quantum finite automaton has an uncountable infinity of states, as the set of all possible states is the set of all points in complex projective space. Thus, quantum finite automata, as well as finite state machines, are special cases of a more general idea, that of a topological automaton, where the set of states is a topological space,
and the state transition functions are taken from the set of all
possible functions on the space. Topological automata are often called M-automata, and are simply the augmentation of a semiautomaton with a set of accept states, where set intersection determines whether the initial state is accepted or rejected.
In general, an automaton need not strictly accept or reject an input; it may accept it with some probability
between zero and one. Again this is illustrated by the quantum finite
automaton, which only accepts input with some probability. This idea is
again a special case of a more general notion, the geometric automaton or metric automaton, where the set of states is a metric space,
and a language is accepted by the automaton if the distance between the
initial point, and the set of accept states is sufficiently small with
respect to the metric.
CHAPTER 2 * LANGUAGES
In English we distinguish the three different entities: letters, words and sentences.
There is a certain parallelism between the fact that group of letters
make up words and the fact that group of words make up sentences. Not
all collection of letters form a valid word, and not all collection of
words form a valid sentences. The analogy can be continued. Certain
groups of sentences make up coherent paragraphs, certain groups of
paragraphs make up coherent stories and so on.
The same situation also exist with computer language. Certain character strings are recognizable words
(
GOTO, END. ) Certain string of words are recognizable commands. Certain
sets of commands become a program (with or without data). To construct
a general theory that unifies all these examples, it is necessary to
adopt a definition of a most “universal language structure”,
that is, a structure in which the decision of whether a given string of
units constitutes a valid larger unit is not a matter of guess work but
is based on explicitly stated rules. It is very hard to state all the
rules for the language “spoken English”, since many seemingly incoherent
strings of words are actually understandable utterances. This is due to
slang, idiom, dialect, and our ability to interpret poetic metaphor and
to correct unintentional grammatical errors in the sentences we hear. Language
will be considered solely as symbols on paper and not as expression of
ideas in the minds of humans. In this basic model, language is not
communication among intellects, but a game of symbols with formal
rules. The term formal emphasizes that it is the form of the string of symbols we are interested in, and not the meaning.
Automata plays a major role in compiler design and parsing. The basic concepts of symbols, words, alphabets and strings are common to most descriptions of automata. These are the following :
Symbol An arbitrary datum which has some meaning to or effect on the machine. Symbols are sometimes just called "letters".
Kleene closure
A language may be thought of as a subset of all possible words. The set
of all possible words may, in turn, be thought of as the set of all
possible concatenations of strings. Formally, this set of all possible
strings is called a free monoid. It is denoted as Σ *, and the superscript * is called the Kleene star.
Alphabet is a finite set of symbols out of which we build structures. An alphabet is denoted by Σ, which is the set of letters in an alphabet.
Language is a specified set of strings of characters, formed by symbols in a given alphabet. May or may not be infinite. Word is a finite string formed by the concatenation of a number of symbols. Words are those strings that are permissible in the language.
Empty or null string is a string that has no letters and is denoted by the symbol L. No matter what language is considered, the null string is always L.
Two words are considered the same if all their letters are the same and
in the same order so there is only one possible word of no letters.
For clarity, we do not allow the symbol L to be part of the alphabet for any language.
There is a difference between the word that has no letters L and the language that has no words. The null set Æ is use to denote the language that has no words. It is not true that L is a word in the language Æ since this language has no words at all. If a language L does not contain the word L and we wish to add it to L, we use the “union of sets” operation denoted by “+” to form L + { L }. This language is not the same as L, however L + Æ is the same as L because there is no new word that has been added.
Formal Language
A formal language is a set of words, i.e. finite strings of letters, or symbols. The inventory from which these letters are taken is called the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar. Formal languages are a purely syntactical notion, so there is not necessarily any meaning
associated with them. To distinguish the words that belong to a
language from arbitrary words over its alphabet, the former are
sometimes called well-formed words (or, in their application in logic, well-formed formulas).
Formal languages are studied in the fields of logic, computer science and linguistics. Their most important practical application is for the precise definition of syntactically correct programs for a programming language.
The branch of mathematics and computer science that is concerned only
with the purely syntactical aspects of such languages, i.e. their
internal structural patterns, is known as formal language theory.
Although it is not formally part of the language, the words of a formal language often have a semantical
dimension as well. In practice this is always tied very closely to the
structure of the language, and a formal grammar (a set of formation
rules that recursively defines the language) can help to deal with the
meaning of (well-formed) words. Well-known examples for this are "Tarski's definition of truth" in terms of a T-schema for first-order logic, and compiler generators like
lex and yacc.Words over an alphabet
An alphabet, in the context of formal languages can be any set, although it often makes sense to use an alphabet in the usual sense of the word, or more generally a character set such as ASCII. Alphabets can also be infinite; e.g. first-order logic is often expressed using an alphabet which, besides symbols such as Ù , Ø , " and parentheses, contains infinitely many elements x0, x1, x2, … that play the role of variables. The elements of an alphabet are called its letters.
A word over an alphabet can be any finite sequence, or string, of letters. The set of all words over an alphabet Σ is usually denoted by Σ* (using the Kleene star). For any alphabet there is only one word of length 0, the empty word, which is often denoted by e, io9ε or Λ. By concatenation
one can combine two words to form a new word, whose length is the sum
of the lengths of the original words. The result of concatenating a
word with the empty word is the original word. In some applications,
especially in logic, the alphabet is also known as the vocabulary and words are known as formulas or sentences; this breaks the letter/word metaphor and replaces it by a word/sentence metaphor.
English is the most familiar example of a language. The alphabet is the usual set of letters plus the apostrophe and hyphen and is denoted by the Greek upper case letter sigma, S.
S = { a b c d e . . . z ‘ - }
Upper case letters are also included in S.
We can now specify which strings of these letters are valid words in
the language by listing them all, as is done in a dictionary. If we call
this language as ENGLISH-WORDS, then
ENGLISH-WORDS = { all the words ( main entries ) in a standard dictionary }
If G
( capital letter gamma ) make a formal definition of the language of
the sentences in English, then, our alphabet is the entries in the
dictionary.
G = { the entries in a dictionary, plus a blank space, plus the usual punctuation marks }
In general, the abstract languages treated will be defined in one of
two ways. Either they will be presented as an alphabet and the
exhaustive list of all valid words, or else they will be presented as an
alphabet and a set of rules defining the acceptable words. Earlier , it
was mentioned that a language can be defined by presenting the alphabet
and then specifying which strings are words. The word “specify” is
trickier than we may at first supposed.
Consider
the example of the language MY-PET. The alphabet of this language is {
a c d g o t }. The possible words are : MY-PET = {cat, dog, goat,
toad }.
Consider an alphabet having only one letter, the letter x ; S = { x },
we can define a language by saying that any nonempty string of alphabet character is a word.
L1 = { x xx xxx xxxx xxxxx . . . } or alternately L1 = { xn for n = 1 2 3 . . . }
Because of the way we define it, this language does not include the null string.
Concatenation is
an operation wherein two strings are written down side by side to form a
new longer string. If xx is concatenated with xxxx , xxxxxx is formed.
The words in this language are clearly analogous to the positive
integers, and the operation of concatenation is analogous to addition.
If xn is concatenated with xm , the word is xn + m.
If a = xx and b = xxx, then if a is concatenated with b ð ab = xxxxx.
It
is not always true that when two words are concatenated they produce
another word in the language. For example if the language is :
L2 = { x xxx xxxxx xxxxxxx . . . } = { xodd } = { x2n + 1 for n = 0 1 2 3 . . . }
a = xxx , b = xxxxx are both words in L2 but their concatenation ab = xxxxxxxx is not in L2.
In the examples, when we concatenate a with b we get the same result when we concatenate b with a.
Thus, ab = ba , but this does not hold for all languages. In
English when we concatenate “house” and “fly” we get “housefly” which
is a word but distinct from “flyhouse”, which is a different thing --
not because they have different meanings but because they are different
words.
Consider another language. Let us begin with the alphabet S = { 0 1 2 3 4 5 6 7 8 9 } and define the set of words : L3
= { any finite string of alphabet letters that does not start with the
letter 0 }. This language looks like the set of all positive integers in
base 10. “Looks like” is used instead of “is” because L3 is only a formal collection of strings of symbols. The integers have other mathematical properties If L3 is to be defined including the string ( word ) 0, then
L3 = { any finite string of alphabet letters that, if it starts with a 0 , has no more letters after the first }.
The box n
is used as an end marker. An illustration starts with a heading and
terminates with and end marker. An old fashioned end marker denoting
that a proof is finished is Q. E. D. The box serves the purpose.
Definition : The function “Length of a string” is the number of letters in the string.
If a = xxxx in the language L1 then length (a ) = 4 or directly length ( xxxx ) = 4.
If c = 526 in the language L3 , then length (c ) = 3 or directly length ( 526 ) = 3.
In any language that includes the empty string L , length ( L ) = 0
For any word w in any language, if length ( w ) = 0 then w = L.
Consider the language L4 = { L x xx xxx xxxx . . . } = { xn for n = 0 1 2 3 . . . }
Here we say, x 0 = L and not x 0 = 1 as in algebra. n
Definition : Reverse function.
If a is a word in some language L, then reverse ( a ) is the same
string of letters spelled backward, called the reverse of a even if this
backward string is not a word in L.
Examples : 1. reverse ( xxx ) = xxx 2. reverse ( 358 ) = 853
3. In L3 reverse ( 650 ) = 056 which is not a word in L3. n
Definition : Let us define a new language called PALINDROME over the alphabet , S = { a , b }.
PALINDROME = { L , and all strings x such that reverse ( x ) = x } n
PALINDROME = { L, a, b, aa, bb, aaa, aba, bab, bbb, aaaa, abba . . . }
Definition : Given an alphabet S, we wish to define a language in which any string of letters from S is a word, even the null string. This language, we shall call the closure of the alphabet. It is denoted by writing a star ( asterisk ) after the name of the alphabet as a superscript, S*. This notation is sometimes known as the Kleene star after the logician who was one of the founders of this subject.
Examples : 1. If S = { x } , then S* = L4 = { L x xx xxx xxxx . . . }
2. If S = { 0 , 1 }, then S* = { L 0 1 00 01 10 11 000 001 . . . }
3. If S = { a , b , c }, then S* = { L a b c aa ab ac ba bb bc ca cb cc aaa . . . } n
We can think of the Kleene star
as an operation that makes an infinite language of strings of letters
out of an alphabet. Infinite here means indefinitely many words each of
finite length.
NOTE
: When we wrote out the first several words in the language, we put
them in size order ( words of shortest length first ) and then listed
all the words of the same length alphabetically.
Kleene star
In mathematical logic and computer science, the Kleene star (or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*. It is widely used for regular expressions, which is the context in which it was introduced by Stephen Kleene to characterise certain automata.
If V is a set of strings then V* is defined as the smallest superset of V that contains λ (the empty string) and is closed under the string concatenation operation. This set can also be described as the set of strings that can be made by concatenating zero or more strings from V.
If V is a set of symbols or characters then V* is the set of all strings over symbols in V, including the empty string.
Definition and notation :
Given V0 = { l } define recursively the set
V i + 1 = { wv : w ÃŽ Vi and v ÃŽ V } where i ³ 0
If V is a formal language, then the i-th power of the set V is shorthand for the concatenation of set V with itself i times. That is, Vi can be understood to be the set of all strings of length i, formed from the symbols in V.
The definition of Kleene star on V is V* = È Vi = { l } È V1 È V2 È V3 È . . .
i ÃŽN
That is, it is the collection of all possible finite-length strings generated from the symbols in V.
In some formal language studies, (e.g. AFL Theory) a variation on the Kleene star operation called the Kleene plus is used. The Kleene plus omits the V0 term in the above union. In other words, the Kleene plus on V is
V + = È Vi = V1 È V2 È V3 È . . .
i ÃŽN+
Example of Kleene star applied to set of strings:
{"ab",
"c"}* = {λ, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc",
"abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}
Example of Kleene star applied to set of characters:
{'a', 'b', 'c'}* = {λ, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", ...}
Example of Kleene star applied to the empty set:
Æ* = { l }
Example of Kleene plus applied to the empty set:
Æ + = Æ Æ* = { } = Æ
Generalization Strings form a monoid
with concatenation as the binary operation and λ the identity element.
The Kleene star is defined for any monoid, not just strings.
Definition
: If S is a set of words, then by S* is the set of all finite
strings formed by concatenating words from S, where any word may be used
as often as we like, and where the null string is also included.
Example : If S = { aa , b }, then S* = { L plus any word composed of factors of aa and b }
= { L plus all strings of a’s and b’s in which the a’s occur in even clumps }
= { L b aa bb aab baa bbb aaaa aabb baab bbaa bbbb aaaab aabaa aabb baaaa
baabb bbaab bbbaa bbbbb . . . }
The
string aabaaab is not in S* since it has a clump of a’s of length 3.
The phrase clump of “a’s” has not been properly defined, but we know
what it means anyway.
Example : Let S = { a , ab }, then
S* = { L plus any word composed of factors of a and ab }
= {L plus all strings of a’s and b’s except those that start with b and those that contain a double b}
= { L a aa ab aaa aab aba aaaa aaab aaba abaa abab aaaaa aaaab aaaba aabaa
aabab abaaa abaab ababa . . . }
“Double
b” means the substring bb. For each word in S* every b must have an a
immediately to its left. The substring bb is impossible, as it is
starting with a b. Any string without the substring bb that begins with
an a can be factored into terms of ( ab ) and ( a ). n
To
prove that a certain word is in the closure language S*, we must show
how it can be written as a concatenate of words from the base set S. In
the above previous example, to show that abaab is in S*, we factor as
follows : abaab = ( ab ) ( a ) ( ab ) These factors are all in the
set S; hence their concatenation is in S*. This is the only way to
factor this string, hence the factoring is unique.
Sometimes the factoring is not unique, i.e.
S = { xx , xxx }, then S* = { L and all strings of more than one x }
= { xn for n = 0, 2, 3, 4, 5, . . . }
= { L xx xxx xxxx xxxxx xxxxxx . . . }
Note that x is not in S*. The string xxxxxxx is in this closure for any of this three reasons :
( xx ) ( xx ) ( xxx ) or ( xx ) ( xxx ) ( xx ) or ( xxx ) ( xx ) ( xx ) .
Important
to note here that the parenthesis ( ) are not letters in the alphabet
but are used for the sole purpose of demarcating the ends of the
factors.
Proof by Constructive Algorithm – a method of proof based on showing that something exists ( i.e. by factoring) because we can describe how to create it.
If the alphabet has no letters, then its closure is the language with the null string as its only word.
Symbolically, if S = f , then S* = { L }. This is not the same as if S = { L }, then S* = { L }.
An alphabet may look like a set of one-letter words. If for some reason
we wish to modify the concept of closure to refer only to the
concatenation of some ( not zero ) strings from a set S, se use the
notation + instead of *.
Example :
If S = { x }, then S + = { x xx xxx xxxx . . . } which is the language L1 discussed before.
If S = { xx , xxx }, then S + is the same as S* except for the word L which is not in S + . This is not to say that S + cannot in general contain the word L. It can, on condition that S contains the word L. In this case L is in S + , since it is the concatenation of some word from S ( L
itself ). Anyone who does not think that the null string is confusing
has missed something. It is already a problem, and it gets worse later.
If S is the set of three words, S = { w1 w2 w3 }, then
S + = { w1 w2 w3 w1w1 w1w2 w1w3 w2w1 w2w2 w2w3 w3w1 w3w2 w3w3
w1w1w1 w1w1w2 . . . }. No matter what the words w1, w2 and w3 are.
If w1 = aa, w2 = bbb and w3 = L , then S + = { aa bbb L aaaa aabbb . . . }.
The
words in the set S are listed above in the order corresponding to
their w-sequencing , not in the usual size-alphabetical order.
Applying
the closure operator twice, yields the closure of S* or ( S* )* =
S**. The closure operator apply to infinite sets as well as to finite
sets.
THEOREM : For any set S of strings we have S* = S**.
Example : S = { a , b }, then S* is clearly all strings of two
letters a and b of any finite length. Taking strings from S* and
concatenate them and say we have concatenated ( aaba ) , ( baaa ) and
(
aaba ). The result ( aababaaaaaba ) is no more than a concatenation
of the letters a and b, just as with all elements of S*. ( aaba ) (
baaa ) ( aaba )
[ ( a ) ( a ) ( b ) ( a ) ] [ ( b ) ( a ) ( a ) ( a ) ] [ ( a ) ( a ) ( b ) ( a ) ]
( a ) ( a ) ( b ) ( a ) ( b ) ( a ) ( a ) ( a ) ( a ) ( a ) ( b ) ( a )
Proof
: Every word in S** is made up of factors from S*. Every factor from
S* is made up of factors from S. Therefore, every word in S** is made
of factors from S. Therefore, every word in S** is also a word in
S* which can be written in the form S** Ì S*.
The symbol “ ÃŒ ” means “is contained in or equivalent to ”. In general, it is true that for any set A we know that A ÃŒ A*, since in A* we can chose as a word any one factor from A. So if we consider A to be our set S* then we have : S* ÃŒ S** .
Together, these two inclusions prove that S* = S** .
Exercise #s 2, 3, 4, 17 page 24 – 25.
CHAPTER 3 * RECURSIVE DEFINITION
– is characteristically a three-step process.
1) specify some basic objects in the set.
2) Give rules for constructing more objects in the set from the ones we already know.
3) Declare that no objects except those constructed in this way are allowed in the set.
Recursive language
A recursive language in mathematics, logic and computer science, is a type of formal language which is also called recursive, decidable or Turing-decidable. The class of all recursive languages is often called R, although this name is also used for the class RP.
This type of language was not defined in the Chomsky hierarchy of (Chomsky 1959).
Definitions
There are two equivalent major definitions for the concept of a recursive language: A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language.
A recursive language is a formal language for which there exists a Turing machine which will, when presented with any input string,
halt and accept if the string is in the language, and halt and reject
otherwise. The Turing machine always halts; it is known as a decider and is said to decide the recursive language.
All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive.
Closure properties
Recursive languages are closed under the following operations. That is, if L and P are two recursive languages, then the following languages are recursive as well:
· the concatenation L o P
· the union L È P
· the intersection L Ç P
· the complement of L
· the set difference L − P
The last property follows from the fact that the set difference can be expressed in terms of intersection and complement.
If we try to define a set of even positive integers. One standard way of defining this set is :
EVEN is the set of all positive whole numbers divisible by 2; or EVEN is the set of all 2n,
where n = 1 2 3 4 . . . A third method is by recursive definition. EVEN is defined by these three rules:
Rule 1 : 2 is in EVEN.
Rule 2 : If x is EVEN then so is x + 2.
Rule 3 : The only elements in the EVEN are those that can be produced from the two rules above.
Ex. 1. Prove that 10 is in the EVEN set.
By defn 1) divide 10 by 2, there is no remainder; hence 10 is in EVEN set
By defn 2) 10 = ( 5 )( 2 ) ; hence 10 is in EVEN.
By defn 3) recursive definition : by rule 1, we know 2 is in EVEN; then by rule 2 we know that
2 + 2 = 4 is in EVEN. Since 4 is in EVEN then by rule 2 , 4 + 2 = 6 is in EVEN. By rule 2,
6 + 2 = 8 is in EVEN. By rule 2 , 8 + 2 = 10 is in EVEN set; hence 10 is in EVEN.
Alternately; the set EVEN is defined by these rules :
Rule 1 : 2 is in EVEN.
Rule 2 : If x and y are both in EVEN then so is x + y.
Rule 3 : No number is in EVEN unless it can be produced by Rules 1 and 2.
To solve the above example :
By rule 1 : 2 is in EVEN
By rule 2 : x = 2 , y = 2 ® 4 is in EVEN
By rule 2 : x = 2 , y = 4 ® 6 is in EVEN
By rule 2 : x = 4 , y = 6 ® 10 is in EVEN.
A polynomial is a finite sum of terms each of which is of the form a
real number times a power of x ( that may be x0 = 1 ).
The set POLYNOMIAL is defined by these four rules :
Rule 1 : Any number is in POLYNOMIAL.
Rule 2 : The variable x is in POLYNOMIAL.
Rule 3 : If p and q are in POLYNOMIAL, then so are p + q and ( p ) and pq.
Rule 4 : POLYNOMIAL contains only those things which can be created by the 3 rules above.
Ex. 2. Show that 5x2 + 4x – 8 is in POLYNOMIAL.
By rule 1 : 5 is in POLYNOMIAL
By rule 2 : x is in POLYNOMIAL
By rule 3 : ( 5 )( x ) is in POLYNOMIAL, call it 5x
By rule 3 : ( 5x )( x ) is in POLYNOMIAL, call it 5x2
By rule 1 : 4 is in POLYNOMIAL
By rule 3 : ( 4 )( x ) is in POLYNOMIAL
By rule 3 : 5x2 + 4x is in POLYNOMIAL.
By rule 1 : –8 is in POLYNOMIAL
By rule 3 : 5x2 + 4x + (–8 ) = 5x2 + 4x – 8 is in POLYNOMIAL.
Ex. 3. Show that 24 is in EVEN set
Ex. 4. Show that 2x2 – 3x + 2 is in POLYNOMIAL.
Ex. 5. Show that 7x2 + 3x – 11 is in POLYNOMIAL.
Ex. 6. Show that x2 – 12x + 18 is in POLYNOMIAL.
Arithmetic Expressions ( AE )
Supposed we ask ourselves what constitutes a valid arithmetic
expressions that can be typed on one line, in a form digestible by
computers. The alphabet of this language is :
S = { 0 1 2 3 4 5 6 7 8 9 + - * / ( ) }
It is obvious that the following strings are not good :
( 3 + 5 ) + 6 ) 2( /8 + 9 ) ( 3 + ( 4 - ) 8 ) 2 ) – ( 4
( 3 + 5 ) + 6 ) – contains an unbalanced parenthesis.
2( / 8 + 9 ) – contains a forbidden substring ( /
( 3 + ( 4 – ) 8 ) – contains the forbidden substring – )
2 ) – ( 4 – contains a close parenthesis before the corresponding open parenthesis.
// and */ are also forbidden in arithmetic expressions.
The most natural way of defining a valid arithmetic expression is by using recursive definition.
The definition can be written as :
Rule 1 : Any number of ( positive, negative, or zero ) is in AE.
Rule 2 : If x is in AE, then so are ( x ) and – ( x ).
Rule 3 : If x and y are in AE, then so are
( i ) x + y ( if the first symbol in y is not – )
( ii ) x – y ( if the first symbol in y is not – )
( iii ) x * y
( iv ) x / y
( v ) x ** y ( our notation for exponentiation )
This is the most natural definition because even if we have not
articulated at this point, it truly is the method for recognizing
arithmetic expression in real life. Given the expression with
( 2 + 4 ) * ( 7 * ( 12 – 4 ) / 4 * 2 ( 2 + 8 ) – 1
and asked to determine if it is a valid expression, we do not really scan over the string looking for forbidden
substrings or count the parentheses. This can broken down into components and verify whether it is ok or not.
Clear expressions : 2 + 3 + 4 , 12 – 3 + 4
Ambiguous expressions : 8/4/2 which may be equal to 4 or 1
3 + 4 * 5 which may be equal to 23 or 35
Hence, we adopt conventions for operator hierarchy and left to right
execution. By applying Rule 2, we can place enough parenthesis to avoid
any confusion. This definition adequately defines the language of all
valid strings of symbols for arithmetic expressions. Remember that the
ambiguity in the string 8/4/2 is a problem of meaning. There is no
doubt that the string is a word in AE, only doubt about what it means.
This definition determines the set AE in a manner useful for proving
many theorems about arithmetic expressions.
Theorem 2 : An arithmetic expression cannot contain the character $.
Proof by constructive algorithm:
$ is not part of any number, so it cannot be introduced into an AE by
Rule 1. If the character string x does not contain the character $, then
neither do the strings ( x ) and – ( x ), so it cannot be introduced
into an AE by Rule 2. If neither x nor y contains the character $,
then neither do any of the expressions defined by Rule 3. Therefore, the
character $ can never get into an AE.
Theorem 3 : No AE can begin or end with the symbol /.
Proof by constructive algorithm:
No number begins or ends with this symbol, so it cannot occur by Rule
1. Any AE formed by Rule 2 must begin and end with parentheses or begin
with a minus sign, so the / cannot be introduced by Rule 2. If x does
not begin with a / and y does not end with a /, then any AE formed by
any clause in Rule 3 will not begin or end with a /. Therefore, these
rules will never produce an expression beginning or ending with a /.
( The symbol / in computer science is “slash”, other names are “oblique
stroke”,
“solidus” or “virgule”).
Theorem 4 : No AE can contain the substring //.
Proof
: For variation, we shall prove this by contradiction, even though a
direct argument similar to those above could easily be given.
Let us suppose that there were some AE’s that contained the
substring //, but there is no shorter word in AE that contains this
substring. There may be more strings of the same length as w that
contains //, but it does not matter which of these we begin with and
choose to call w.
We know that w like all words in AE, is formed by some sequence of
applications of the Rules 1, 2 and 3. The first question is: Which was
the last rule used in the production of w ? It must have been Rule
3(iv). If it were Rule 3(iii), for instance, then the double slash must
either be found in the x part or the y part. But x and y are presumed to
be in AE so this would mean that there is some shorter word in AE than w
that contains the substring //, which contradicts the assumption that w
is the shortest, similarly, we can eliminate all the other
possibilities. Therefore the last rule used to produce w must have
been 3 (iv).
Now, since the // can have been contributed to w from the x
part alone or from the y part alone ( or else x or y) are shorter
words in AE with a double slash , it must have been included by finding
an x part that ended in / or a y part that begin with a /. But since
both x and y are AE’s, our previous theorem says that neither case can
happen. Therefore even Rule 3(iv) cannot introduce the substring //.
Therefore, there is no possibility left for the last rule from which w
can be constructed. Therefore, w cannot be in the set AE. Therefore
there is no shortest AE that contains the substring //. Therefore,
nothing in the set AE can have the substring //. n
This method of argument should familiar. It is similar to the proof that { xx, xxx }* contains al xn , for n ¹ 1.
Another
common use of the recursive definitions is to determine what
expressions are valid in Symbolic Logic. We shall be interested in one
particular branch of Symbolic Logic called Sentential Calculus or the
Propositional Calculus. The version we shall use here uses only
negation Ø and implication ®
along with the phrase variables, although conjunction and disjunction
could easily be added to the system. The valid expressions in this
language are traditionally called WFF’s for Well-Formed Formulas. As with AE, parentheses are letters in the alphabet.
No comments:
Post a Comment