Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 305 Operations on Languages SupposeLandMare languages over an alphabetA. Then the “conca ...

306 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12 (3)L(r∗)=(L(r))* (the Kleene closure ofL(r)). (4)L(r 1 ∨r 2 )=L(r 1 )∪L(r 2 )(the un ...

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 307 Such an automatonMis denoted byM=(A,S,Y,s 0 ,F)when we want to indicate its five par ...

308 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12 Fig. 12-2 LanguageL(M)Determined by an AutomatonM Each automatonMwith input alphabet ...

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 309 Fig. 12-3 Sinceb^2 is accepted, but notlorb, we need three states,s 0 , the initial ...

310 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12 12.6Grammars Figure 12-5 shows the grammatical construction of a specific sentence. ...

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 311 EXAMPLE 12.9 The following defines a grammarGwithSas the start symbol: V={A, B, S, a ...

312 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12 Types of Grammars Grammars are classified according to the kinds of production which ...

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 313 Derivation Trees of Context-Free Grammars Consider a context-free (Type 2) grammarG. ...

314 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12 Machines and Grammars Theorem 12.4 tells us that the regular languages correspond to ...

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 315 LANGUAGES 12.6. LetA={a, b}. Describe verbally the following languages overA(which a ...

316 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12 12.12. LetA={a, b, c}and letw=abc. State whether or notwbelongs toL(r)where: (a) r=a ...

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 317 Fig. 12-8 12.17. Describe the wordswin the languageLaccepted by the automatonMin Fig ...

318 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12 12.21. Repeat Problem 12.20 except now letNaccept preciselyL(M)∪L(M′). Again, letS×S ...

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 319 Fig. 12-10 (b) The leaves show thataandbmust be terminals, and the internal vertices ...

320 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12 LANGUAGES 12.34. LetL={a^2 ,ab}andK={a, ab, b^2 }. Find: (a)LK; (b)KL; (c)L∨K; (d)K∧ ...

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 321 GRAMMARS 12.47. Determine the type of grammarGwhich consists of the productions: (a) ...

322 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12 Fig. 12-13 Fig. 12-14 Fig. 12-15 12.47. (a) Type 2; (b) Type 0; (c) Type 3. 12.48. S ...

CHAPTER 13 Finite State Machines and Turing Machines 13.1Introduction This chapter discusses two types of “machines.” The first ...

324 FINITE STATE MACHINES AND TURING MACHINES [CHAP. 13 (6) Output functiong:S×A→Zdefined by: g(s 0 ,a)=x, g(s 1 ,a)=x, g(s 2 ,a ...