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.
S = { Ø ® ( ) a b c d . . . }
There are other symbols sometimes used for negation, such as ⌐ , – , and the rules for forming WFF’s are :
Rule 1: Any single Latin letter is a WFF.
a b c d . . .
Rule 2 : If p is a WFF, then so are ( p ) and Ø p .
Rule 3 : If p and q are WFF’s, then so is p ® q .
Some sequences of applications of these rules enables us to show that :
p ® q (( p ® q ) ® q ) is a WFF. Without too much difficulty we can also show that :
p ® ® q ( p ® p ) p) ® p ( are not all WFF’s.
No comments:
Post a Comment