1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 20
Текст из файла (страница 20)
} for somep,q E N.(a) (Easy) Show that if L ~ {a}* and {n : an E L} is an arithmeticprogression, then L is regular.(b) Show that if L ~ {a} * and {n : (l n E L} is a union of finitely manyarithmetic progressions, then L is regular.90Chapter 2: FINITE AUTOMATA(c) (Harder) Show that if L ~ {a}' is regular, then {n : an E L} is a unionof finitely many arithmetic progressions.
(This is the converse of Part(b). )(d) Show that if ~ is any alphabet and L ~ ~* is regular, then {Iwl : wEL} is a union of finitely many arithmetic progressions. (Hint: Use Part(c). )2.4.2. Let D = {O, I} and let T = D x D x D. A correct addition of two numbers inbinary notation can be pictured as a string in T* if we think of the symbolsin T as vertical columns. For example,+010 10 1 1 0101 1would be pictured as the following string of four symbols.Show that the set of all strings in T* that represent correct additions is aregular language.2.4.3. Show that each of the following is or is not a regular language.
The decimalnotation for a number is the number written in the usual way, as a stringover the alphabet {O, 1, ... , 9}. For example, the decimal notation for 13 isa string of length 2. In unary notation, only the symbol I is used; thus 5would be represented as I I I I I in unary notation.(a) {w: w is the unary notation for a number that is a multiple of 7}.(b) {w: w is the decimal notation for a number that is a multiple of 7}(c) {w: w is the unary notation for a number n such that there is a pairp, p + 2 of twin primes, both greater than n}(d) {w: w is, for some n 2: 1, the unary notation for IOn}(e) {w: w is, for some n 2: 1, the decimal notation for IOn}(f) {w: w is a sequence of decimal digits that occurs in the infinite decimalexpansion of 1/7} (For example, 5714 is such a sequence, since 1/7 =0.14285714285714 ...
)2.4.4. Prove that {anbamba m+n : n, m 2: I} is not regular.2.4.5. Using the pumping theorem and closure under intersection, show that thefollowing are not regular.(a) {ww R : w E {a,b}'}(b) {ww: w E {a, b} *}(c) {wID: w E {a, b}'}, where ID stands for w with each occurrence of areplaced by b, and vice versa.2.4: Languages That Are and Are Not Regular912.4.6. Call a string x over the alphabet {(,)} balanced if the following hold: (i) inany prefix of x the number of ('S is no smaller than the number of )'s; (ii)the number of ('S in x equals that of )'s.
That is, x is balanced if it could bederived from a legal arithmetic expression by omitting all variables, numbers, and operations. (See the next chapter for a less awkward definition.)Show that the set of all balanced strings in {(,)} * is not regular.2.4.7. Show that for any deterministic finite automaton M = (K,Y:;,r5,s,F), Maccepts an infinite language if and only if M accepts some string of lengthgreater than or equal to IKI and less than 21KI.2.4.8. Are the following statements true or false? Explain your answer in eachcase. (In each case, a fixed alphabet y:; is assumed.)(a) Every subset of a regular language is regular.(b) Every regular language has a regular proper subset.(c) If L is regular, then so is {xy : x ELand y ~ L}.(d) {1lJ: W = llJR} is regular.(e) If L is a regular language, then so is {1lJ : w ELand llJR E L}.(f) If C is any set of regular languages, then UC is a regular language.(g) {xyx R : x,y E Y:;*} is regular.2.4.9. The notion of a deterministic 2-tape finite automaton was defined in Problem 2.1.5.
Show that {(anb,ambP) : n,m,p > O,n = m or n = p} is notaccepted by any deterministic 2-tape finite automaton. (Hint: Suppose thisset were accepted by some deterministic 2-tape finite automaton AI. ThenlIf accepts (anb, an+1b n ) for every n. Show by a pumping argument that italso accepts (anb, an+1b TlH ) for some n 2: 0 and q > 0, a contradiction.) ByProblem 2.3.9, then, nondeterministic 2-tape finite automata cannot alwaysbe converted to deterministic ones, and by Problem 2.1.5, the sets acceptedby deterministic 2-tape finite automata are not closed under union ..4.10.
A 2-head finite automaton is a finite automaton with two tape headsthat may move independently, but from left to right only, on the input tape.As with a 2-tape finite automaton (Problem 2.1.5), the state set is dividedinto two parts; each part corresponds to reading and moving one tape head.A string is accepted if both heads wind up together at the end of the stringwith the finite control in a final state. 2-head finite automata may be eitherdeterministic or nondeterministic.
Using a state-diagram notation of yourown design, show that the following languages are accepted by 2-head finiteautomata.(a) (anb n : n;?:OJ(b) {llJCllJ: 1lJ E {a, b}'}(c) {a 1ba 2 ba 3 b ... ba k b: k 2: I}In which cases can you make your machines deterministic?92Chapter 2: FINITE AUTOMATA2.4.11. This problem establishes a stronger version of the Pumping Theorem 2.4.1;the goal is to make the "pumped" part as long as possible.
Let M =(K, ~,6, s, F) be a deterministic finite automaton, and let w be any stringin L(/o.1) of length at least IKI. Show that there are strings x, y, and z suchthat w = xyz, Iyl ~ (Iwl - IKI + l)/IKI, and xyn z E L(M) for each n ~ O.2.4.12. Let D = {O, I} and let T = D x D x D. A correct multiplication of twonumbers in binary notation can also be represented as a string in T*.
Forexample, the multiplication 10 x 5 = 50, oro0 1 0 1 0x0001011 100 1 0would be pictured as the following string of six symbols.Show that the set of all strings in T* that represent correct multiplicationsis not a regular language. (Hint: Consider the multiplication (2n + 1) x(2n + 1).)2.4.13. Let L <;;; ~* be a language, and define Ln = {x E L: Ixl :::; n}. The densityof L is the function dL(n) = ILnl.(a) What is the density of (a U b)*?(b) What is the density of ab*ab * ab*a?(c) What is the density of (ab U aab)*?(d) Show that the density of any regular language is either bounded fromabove by a polynomial, or bounded from below by an exponential (afunction of the form 2cn for some n).
In other words, densities of regularlanguages cannot be functions of intermediate rate of growth such asn iogn . (Hint: Consider a deterministic finite automaton accepting L,and all cycles -closed paths without repetitions of nodes- in thestate diagram of this automaton. What happens if no two cycles sharea node? What happens if there are two cycles that share a node?)liiJSTATE MINIMIZATIONIn the last section our suspicion that deterministic finite automata are poormodels of computers was verified: Computation based on finite automata cannot932.5: State Minimizationachieve such trivial computational tasks as comparing the number of a's and thenumber of b's in a string.
However, finite automata are useful as basic partsof computers and algorithms. In this regard, it is important to be able tominimize the number of states of a given deterministic finite automaton, that is,to determine an equivalent deterministic finite automaton that has as few statesas possible. We shall next develop the necessary concepts and results that leadto such a state minimization algorithm.Figure 2-19Given a deterministic finite automaton, there may be an easy way to get ridof several states.
Let us take, for example, the deterministic automaton in Figure2-19, accepting the language L = (ab U ba)* (as it is not very hard to check).Consider state q7. It should be clear that this state is unreachable, becausethere is no path from the start state to it in the state diagram of the automaton.This is the simplest kind of optimization one can do on any deterministic finiteautomaton: Remove all unreachable states and all transitions in and out of them.In fact, this optimization was implicit in our conversion of a nondeterministicfinite automaton to its equivalent deterministic one (recall Example 2.2.4): Weomitted from consideration all states (sets of states of the original automaton)that are not reachable from the start state of the resulting automaton.Identifying the reachable states is easy to do in polynomial time, becausethe set of reachable states can be defined as the closure of {s } under the relation{(p, q) : 6(p, a) = q for some a E ~}.
Therefore,the set of all reachable statescan be computed by this simple algorithm:R:={s};while there is a state pER and a E ~ such that 6(p, a) ~ R doadd 6(p, a) to R.However, the remaining automaton after the deletion of unreachable states(Figure 2-20) still has more states than are really needed, this time for subtlerreasons. For example, states q4 and q6 are equivalent, and therefore they can be94Chapter 2: FINITE AUTOMATAFigure 2-20merged into one state.
What does this mean, exactly? Intuitively, the reason wecall these states equivalent is that, from either state, precisely the same stringslead the automaton to acceptance.Our next definition captures a similar relation between strings that have "acommon fate" with respect to a language.Definition 2.5.1: Let L ~ ~* be a language, and let x, y E ~*. We say that xand yare equivalent with respect to L, denoted x ~L y, iffor all z E ~*, thefollowing is true: xz E L if and only if yz E L.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
