CS 161代做、Java/Python程序代写

日期：2024-04-24 08:52

CS 161, Spring 2024: Homework 2

Homework 2: NFAs and Regular Expressions

0. (Ungraded exercise) We rushed/didn’t get to the exercises at the end of worksheet 3

(copied below for convenience). Make sure you understand what is wrong with these

proofs.

(a) Here is a false statement with a bad proof. What is wrong with the proof?

Theorem (Not actually true). Every binary language is regular.

Proof. Let A be any language. Here is a DFA M:

M q0

0,1

Note that any string in A is accepted by this DFA. Thus, this DFA recognizes A,

so A is regular.

(b) Here is a false statement with a bad proof. What is wrong with the proof?

Theorem (Not actually true). The language A = {00, 11} is not regular.

Proof. Here is a DFA M:

M q0 q1

0 1

1

0

The string 11, which is in A, is not accepted by this DFA. Thus, the DFA M does

not recognize A, so A is not regular.

1. (10 points) Let L be the language of binary strings with at least two 0s or at least

three 1s.

(a) (5 points) Draw a state diagram for an NFA that recognizes L.

(b) (5 points) Recall that an NFA is a 5-tuple N = (Q, Σ, δ, q0, F) for finite set of states

Q, finite set of alphabet characters Σ, transition function δ : Q × Σε → P(Q),

start state q0 ∈ Q, and accept states F ? Q. Describe your NFA as a 5-tuple.

2. (10 points) Prove the following theorem by generalizing the construction from Worksheet 6.

Theorem. The set of regular languages are closed under concatenation.

(c) Sara Krehbiel, Ray Li 1

CS 161, Spring 2024: Homework 2

That is, prove that, for any two regular languages A and B, the language A ? B =

{ab : a ∈ A : b ∈ B} is regular.

3. (5 points) Consider the NFA N = ({1, 2, 3}, {0, 1}, δ, 1, {3}) with δ as depicted below (this is the same one from Quiz 6). Give a regular expression for the language

recognized by this NFA.

N 1 2 3

ε

1

0

1 0

4. (10 points) Find an NFA that recognizes the language of (0?1)? ?(0∪1) (the alphabet is

Σ = {0, 1}). Include both a state diagram and a formal specification of your automaton

as a 5-tuple.

5. (10 points) Let A be the language of strings over Σ = {0, 1} from the first day of class:

A = {1

a01b01a+b

: a, b ≥ 0}. Prove that A is not regular. (An informal interpretation

of this result is: DFAs cannot add in unary) Hint: 1

6. (15 points) We see in class on 4/15 how to convert any k-state NFA into an equivalent

2

k

-state DFA. This problem shows that this exponential blowup in the number of states

is necessary. Let A ? {0, 1}

? be the set of all strings (of length at least 101) that have

a 0 exactly 100 places from the right hand end. That is

A = {w : |w| ≥ 101, w|w|?100 = 0}. (1)

(a) (5 points) Draw the state diagram for an NFA with 101102 states that recognizes

A. (You can use “· · · ” and don’t have to draw all 101102 states, as long as it’s

clear what the states/transitions would be in the omitted states) [Ray: Update: I

think you need 102 states. If you have 103 or 104 states, that’s fine.]

(b) (10 points) Show that no DFA on less than 2100 states can recognize A. Hint:2

1

In this class, we learn several methods for proving a language A is regular: constructing a DFA recognizing A, constructing an NFA recognizing A, finding a regular expression for A. However, we only learn

one method for proving a language is not regular. What is it?

2Give a proof by contradiction and assume such a DFA exists. Apply pigeonhole to all 2100 strings of

length 100 to get two strings x and y of length 100 that end up at the same state after digesting. Derive a

contradiction by considering the strings xz and yz for some carefully chosen string z.

(c) Sara Krehbiel, Ray Li 2