代做CS 3800 Spring 2024 Homework 4调试SPSS

日期：2024-09-12 05:39

CS 3800              Spring 2024

Homework 4

1. [5 Points] Regular Operations. Let Σ = {a, b, c} and consider language A = {ca, b}. List the first twelve elements (in shortlex order) of A∗ .

2. [13 Points] DFA construction. For each of the following languages over the alphabet {a, b}, draw the state transition diagram of a DFA with alphabet {a, b} that recognizes the language. For full credit, try to keep your solution simple (limit the number of states).

(a) ∅

(b) {ε}

(c) {ab, ba}

(d) {w | w starts with a and ends with b}

(e) {w | w has neither aa nor bb as substring}

(f) {w | there exist strings x and y such that w = xaabby}. That is, the language con-sists of those words that have the substring aabb.

3. [8 Points] DFA Complement. Let L = {w ∈ {a, b}* | the number of b’s in w isn’t 3}. For example ε, a, b, ababa, baabbab ∈ L but bbb, bababa ̸∈ L.

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

(b) Apply the methods of Lecture 8a to give the state diagram of a DFA for L.

4. [9 Points] Product method. Let Σ = {a, b, c} and consider languages {a, b}* and {a, c}*.

(a) Draw the state diagrams of finite automata M1 and M2 with alphabet Σ such that

L(M1) = {a, b}* and L(M2) = {a, c}*

To facilitate the following part (b), give distinct names to the states of your au-tomata.

(b) Apply the product construction of lecture 8a to draw the state diagram of a finite automaton M with

L(M) = L(M1) ∪ L(M2) = {a, b}* ∪ {a, c}*

5. [5 Points] NFAs acceptance Which, if any, of the strings below are accepted by the following nondeterministic finite automaton?

(a) aa

(b) aba

(c) ab

(d) aaab

(e) abab

6. [5 Points] NFAs. Let Σ = {a, b} and let

L = {w ∈ Σ* | w contains at least two a’s with exactly 6 characters between them}

For example, aabbababbabab ∈ L because there are exactly 6 characters between the third and the last a but ababbabbab ̸∈ L. Draw the state-diagram of a NFA that accepts L.

7. [10 Points] NFAs. Let Σ = {a, b, c, d} and let

L = {w ∈ Σ* | w ≠ ε and the last character of w appears nowhere else in w}

Draw the state-diagram of a NFA that accepts L.

8. [10 Points] Tint. (Submission is separate from the other problems. Instructions will be posted on Piazza.) Let Σ = {0, 1, 2} and consider the language

L ⊆ Σ*

that consists of all base-3 numerals that are divisible by 7. For example, 01022 ∈ L as 0 · 34 + 1 · 33 + 0 · 32 + 2 · 31 + 2 · 30 = 35 is divisible by 7.

Similarly, 00021, 00021210, , 10010 ∈ L but 02201, 10001 ̸∈ L

Note also, that ε ̸∈ L as the empty word isn’t a numeral .

Design and submit a deterministic finite automaton M such that L(M) = L.

9. [5 Points]. Tint. (Submission is separate from the other problems. Instructions will be posted on Piazza.) Let

A string of symbols from Σ defines two rows of 0s and 1s. Consider each row to be a binary number and let

D = {w ∈ Σ+ | the top row of w is a smaller number than the bottom row}

For example,  ∈ D because, as binary numbers, 0011 < 0100.

Construct a finite automaton that accepts D. Note that, due to the linearity of sym-bols in tint, the columns above have to be represented by strings of length 2. That is, Σ = {00, 01, 10, 11}. And “00 01 10 10” ∈ D because, as binary numbers, 0011 < 0100.