Ch 8. Solutions

1. Let [latex]L[/latex] be the set of strings over [latex]\Sigma = \{ a, b \}[/latex] such that each string contains exactly two occurrences of a and any number of b’s.
3. Length 2: ab; Length 4: aabb; Length 6: aaabbb.
7. Let the grammar [latex]G[/latex] be defined as [latex]S \rightarrow VC \mid CV, V \rightarrow a \mid e \mid i \mid o \mid u, C \rightarrow b \mid c \mid d \mid f \mid g; VC \rightarrow V C VC \mid \epsilon, CV \rightarrow C V CV \mid \epsilon[/latex].
9. Let [latex]L[/latex] be the set of strings over [latex]\Sigma[/latex] such that the first character is a digit, followed by one or more uppercase letters, and ends with a special character.
Let the grammar [latex]G[/latex] be defined as [latex]S \rightarrow D U+ S, D \rightarrow 0 \mid 1 \mid \dots \mid 9, U \rightarrow A \mid B \mid \dots \mid Z, S \rightarrow ! \mid @ \mid \#[/latex], where [latex]U+[/latex] means one or more uppercase letters.
11. Disprove the statement.
13. [latex]S \rightarrow aS \mid aSb \mid a \mid aS, A \rightarrow aA \mid bA \mid \epsilon[/latex]
15. [latex]G_{1}[/latex] and [latex]G_{2}[/latex] generate similar but not identical languages.
17. Not accepted.
21. [latex]\Sigma: \{ 5, 10, 25 \}; q_{0}: 0, q_{5}: 5, q_{10}: 10, \dots, q_{50}: 50[/latex]; [latex]q_{0}[/latex] is the starting state, [latex]q_{50}[/latex] is the accepting state.
Transitions:
From [latex]q_{0}: 5 \rightarrow q_{5}, 10 \rightarrow q_{10}, 25 \rightarrow q_{25}[/latex]
From [latex]q_{5}: 5 \rightarrow q_{10}, 10 \rightarrow q_{15}, 25 \rightarrow q_{30}[/latex]
[latex]\dots[/latex]
and so on until [latex]q_{50}[/latex].
23. [latex]\Sigma[/latex]: {up down}; [latex]F_{1}[/latex]: Floor 1, [latex]F_{2}[/latex]: Floor 2, [latex]F_{3}[/latex]: Floor 3
Transitions: From [latex]F_{1}[/latex]: up [latex]\rightarrow F_{2}[/latex], down [latex]\rightarrow[/latex] invalid (no transition)
From [latex]F_{2}[/latex]: up [latex]\rightarrow F_{3}[/latex], down [latex]\rightarrow F_{1}[/latex]
From [latex]F_{3}[/latex]: up [latex]\rightarrow[/latex] invalid, down [latex]\rightarrow F_{2}[/latex]
27. Prove it.
29. [latex]L = \{ w \in \{ 0, 1 \}^{*} \mid[/latex] the third symbol from the end of [latex]w[/latex] is [latex]1 \}[/latex]
[latex]q_{0}[/latex]: start state, [latex]q_{1}[/latex]: guess state, [latex]q_{2}[/latex]: second-to-last symbol; [latex]q_{3}[/latex]: last symbol; [latex]q_{4}[/latex]: accepting state
Transitions: [latex]q_{0} \rightarrow q_{0}[/latex] on [latex]0[/latex] or [latex]1, q_{0} \rightarrow q_{1}[/latex] on [latex]1, q_{1} \rightarrow q_{2}[/latex] on [latex]0[/latex] or [latex]1, q_{2} \rightarrow q_{3}[/latex] on [latex]0[/latex] or [latex]1, q_{3} \rightarrow q_{4}[/latex]