314 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12Machines and Grammars
Theorem 12.4 tells us that the regular languages correspond to the finite state automata (FSA). There are also
machines, more powerful than the FSA, which correspond to the other grammars.(a) Pushdown Automata:A pushdown automatonPis similar to a FSA except thatPhas an auxiliary stack
which provides an unlimited amount of memory forP. AlanguageLis recognized by a pushdown automaton
Pif and only ifLis context-free.(b)Linear Bounded Automata:A linear bounded automatonBis more powerful than a pushdown automaton.
Such an automatonBuses a tape which is linearly bounded by the length of the input wordw. A language
Lis recognized by a linear bounded automatonBif and only ifLis context-sensitive.(c) Turing Machine:ATuring machineM, named after the British mathematician Alan Turing, uses an infinite
tape; it is able to recognize every languageLthat can be generated by any phase-structure grammarG.
In fact, a Turing machineMis one of a number of equivalent ways to define the notion of a “computable”
function.The discussion of the pushdown automata and the linear bounded automata lies beyond the scope of this text.
We will discuss Turing machines in Chapter 13.SolvedProblems
WORDS12.1. Consider the wordsu=a^2 ba^3 b^2 andv=bab^2. Find: (a)uv;|uv|;(b)vu,|vu|;(c)v^2 ,|v^2 |.
Write the letters of the first word followed by the letters of the second word, and then count the number of letters
in the resulting word.(a) uv=(a^2 ba^3 b^2 )(bab^2 )=a^2 ba^3 b^3 ab^2 ;|uv|= 12
(b) vu=(bab^2 )(a^2 ba^3 b^2 )=bab^2 a^2 ba^3 b^2 ;|vu|= 12
(c) v^2 =vv=(bab^2 )(bab^2 )=bab^3 ab^2 ;|v^2 |= 812.2. Supposeu=a^2 bandv=b^3 ab. Find: (a)uvu;(b)lu,ul,ulv.
(a) Write down the letters inu, thenv, and finallyuto obtainuvu=a^2 b^4 aba^2 b.
(b) Sincelis the empty word,lu=ul=u=a^2 bandulv=uv=a^2 b^4 ab.12.3. Letw=abcd.(a) Find all subwords ofw.(b) Which of them are initial segments?
(a) The subwords are:l,a,b,c,d,ab,bc,cd,abc,bcd,w=abcd. (We emphasize thatv=acdis not a subword
ofweven though all its letters belong tow.)
(b) The initial segments arel,a,ab,abc,w=abcd.12.4. For any wordsuandv, show that:(a)|uv|=|u|+|v|; (b)|uv|=|vu|.
(a) Suppose|u|=rand|v|=s. Thenuvwill consist of therletters ofufollowed by thesletters ofv; hence
|uv|=r+s=|u|+|v|.
(b) Using (a) yields|uv|=|u|+|v|=|v|+|u|=|vu|.12.5. State the difference between the free semigroup on an alphabetAand the free monoid onA.
The free semigroup onAis the set of all nonempty words inAunder the operation of concatenation; it does not
include the empty wordl. On the other hand, the free monoid onAdoes include the empty wordλ.