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

318 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12

12.21. Repeat Problem 12.20 except now letNaccept preciselyL(M)∪L(M′).

Again, letS×S′be the set of states ofNand let (s 0 ,s 0 ) be the initial state ofN. Now let(S×Y′)∪(Y×S′)be

the accepting states inN. The next-state functionGis again defined by

G((s, s′), a)=(F (s, a), F′(s′,a))

ThenNwill accept precisely those words inL(M)∪L(M′).

GRAMMARS

12.22. Define: (a) context-free grammar; (b) regular grammar.

(a) A context-free grammar is the same as a Type 2 grammar, that is, every production is of the formA→β, that

is, the left side is a single variable and the right side is a word in one or more symbols.

(b) A regular grammar is the same as a Type 3 grammar, that is, every production is of the formA→aor of the

formA→aB, that is, the left side is a single variable and the right side is either a single terminal or a terminal

followed by a variable.

12.23. Find the languageL(G)generated by the grammarGwith variablesS,A,B, terminalsa,b, and produc-
tionsS→aB,B→b,B→bA,A→aB.
Observe that we can only use the first production once since the start symbolSdoes not appear anywhere else.
Also, we can only obtain a terminal word by finally using the second production. Otherwise we alternately adda’s
andb’s using the third and fourth productions. Accordingly,

L(G)={(ab)n=ababab···ab|n∈N}

12.24. LetLbe the language onA={a, b}which consists of all wordswwith exactly oneb, that is,

L={b, arb, bas,arbas|r> 0 ,s> 0 }

(a) Find a regular expressionrsuch thatL=L(r).

(b) Find a regular grammarGwhich generates the languageL.

(a) Letr=a∗ba∗. ThenL(r)=L.

(b) The regular grammarGwith the following productions generatesL:

S→(b, aA), A→(b, aA, bB), B→(a, aB)

That is, the letterbcan only appear once in any word derived fromS.Gis regular since it has the required form.

12.25. LetGbe the regular grammar with productions:S→aA,A→aB,B→bB,B→A.

(a) Find the derivation tree of the wordw=aaba.

(b) Describe all wordswin the languageLgenerated byG.

(a) Note first thatwcan be derived fromSas follows:

S⇒aA⇒a(aB)⇒aa(bB)⇒aaba

Figure 12-10(a) shows the corresponding derivation tree.

(b) Using the production 1, then 2, then 3,rtimes, and finally 4 will derive the wordw=aabra wherer≥0.

No other word can be derived fromS.

12.26. Figure 12-10(b)is the derivation tree of a wordwin the languageLof a context-free grammarG.
(a) Findw.(b) Which terminals, variables, and productions must lie inG?

(a) The sequence of leaves from left to right yields the wordw=ababbbba.