Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 3800 Spring 2024

Homework 5

1. [15 Points] Closure properties Let Σ = {0, 1} and consider the languages

L1 = {w ∈ Σ* | w has odd length that is at most 5} and

L2 = {w ∈ Σ* | w ≠ ε and every odd position of w is a 1}.

(a) Draw the state diagram of a DFA for L1.

(b) Draw the state diagram of a DFA for L2.

(c) Use the method from Lecture 9b to draw the state diagram of a NFA for L1 ◦ L2.

2. [8 Points] Closure properties Consider the language

L = {w ∈ {0, 1}* | w contains at least two 0’s and at most one 1}

(a) Give the state diagram of a DFA for L.

(b) Use the method from Lecture 9b to construct the state diagram of a NFA for L*.

3. [8 Points] Subset method. The following nondeterministic finite automaton accepts the set of words from {a, b}* that end in aaa. Use the subset method from lecture 9a to convert this automaton to an equivalent deterministic finite automaton. Draw a state-diagram for your automaton (showing only the reachable states). In your drawing, use proper set notation to clearly label each state of the DFA with the set of states of the NFA that it represents.

4. [10 Points] Subset method. Use the subset method from lecture 9a to convert the fol-lowing nondeterministic finite automaton to an equivalent deterministic finite automaton M = (Q, Σ, δ, s, F). Specify all five components of your automaton, writing δ as a table. You only need to show the reachable states. Use proper set notation to describe the states of your DFA.

5. [20 Points] Comparing Regular Expressions For each of the following statements, state whether it is true or false. Justify your answer (prove the true statements and give counterexamples for the false statements).

(a) abba ∈ a*(ba)*ba*

(b) abba ∈ (ab)*a*(b*a)*

(c) (ab)* = a*b*

(d) b*a* ∩ a*b* = a* ∪ b*

(e) (a ∪ b)* = a* ∪ b*

(f) a(bca)* bc = ab(cab)* c

(g) ∅* = ε*

(h) (a*b*)* = (a*b)*

(i) (ab ∪ a)*a = a(ba ∪ a)*

(j) (a ∪ b)*b(a ∪ b)* = a*b(a ∪ b)*

6. [16 Points] Writing Regular Expressions Let Σ = {a, b}. Write regular expressions for the languages below. In each case, simplify your expression as much as possible.

(a) All strings in Σ* with no more than three b’s.

(b) All strings in Σ* with a number of a’s divisible by 3.

(c) All strings in Σ* that do not end with aa.

(d) All strings in Σ* that do not have a substring aa.

7. [12 Points] Simplifying regular expressions. A regular expression is said to be simpler than another if it involves less operations than the other. For example, a* (1 operation) is simpler than (a*)* (2 operations) and (a ∪ b)c (2 operations) is simpler than ac ∪ bc (3 operations). Rewrite each of the following regular expressions as a simpler regular expression describing the same language. (For full credit simplify as much as possible). Show your work.

(a) ∅* ∪ a* ∪ b* ∪ (a ∪ b)*

(b) (aa)* ∪ a(aa)*

(c) ((a*a) b) ∪ b

(d) (a*b)* ∪ (b*a)*

(e) (ab ∪ b*)*

(f) (a ∪ b)*a (a ∪ b)*

8. [4 Points] From regular expression to NFA. Use the exact procedure from class (lecture 10c) to convert the expression a* ∪ (ab)* to a NFA.

9. [10 Points] From NFA to regular expression. Use the method from class (lecture 10d) to convert the following automaton to a regular expression. First construct the corresponding GNFA (without ∅ labeled edges), then strip states one by one in the following order: strip state 2 first, then state 1, then state 3). Show your work, including the diagrams after each stripping.

10. [7 Points] Tint. (Submission is separate from the other problems)

At XYZ enterprises, employees are asked to choose passwords consisting of symbols from the alphabet Σ = {a, b, 0, 1, Z}. The conditions are

❼ Each password must have length at least 5.

❼ Each password must include at least two letters, one digit, and the special character Z.

For example, aaa0Z and Z00aa are valid passwords, but ab1Z and abab01 are not.

Design a DFA that accepts precisely those words of Σ* that are valid passwords.

Start early: your program may be long.