CSE473 Automata Formal Languages & Computability

CSE 473 Automata Formal Languages and Computability

Fall 2021

Homework 1

(100 points)

1. (10 points) Let ∑ = {a, b}. Define the language

L = { w | w ∈ ∑* and |w| < 5 and a(w) % 2 = 0 } by listing all the strings in this language. 2. (10 points) Prove one of the following by induction on the variable n. Obviously, only one of these can be true. or 3. (10 points) Draw the following directed graph, G(V, E): V = { x | x ≤ 10 and x ∈ } E = { (i, i-2) | 10 > i > 5 and i ∈ } ⋃ { (i, 2*i) | 1 ≤ i ≤ 5 and i ∈ }

Following the conventions in our textbook, is the set of positive natural numbers (i.e., it does not contain 0).

4. (10 points) Let and Show that || = || by giving a bijection between the two sets. Argue that your function is a bijection.

5. (10 points) Consider a social networking site with 100 members and a total of 425 connections. Assume person p has the most friends (or is tied for the most friends) in the database. Prove the tightest possible lower bound on the number of friends of p.

6. (10 points) Consider the alphabet Write the mathematical, 5-tuple definition of a DFA that accepts the language

L = { w | w starts with 1 and has an odd number of 0’s }.

7. (15 points) Consider the alphabet For each of the languages below, create a DFA to accept it. Show all your work if you used operations like complement or union in intermediary steps.

a) L = {, aa, aabb}

b) L = { w | w contains an even number of ’s or an even number of ’s}

Note: Consider 0 to be an even number.

c) L = { w | every in w is preceded by two ’s}

d) L = { w | w does not contain the substring }

e) L = { w | w starts with an and ends with two ’s }

8. (10 points) Consider the alphabet Draw an NFA to accept the language

L = { w | |w| is even and w starts with an or

w contains the substring }.

Assume that 0 is an even number.

9. (15 points) Using the procedure presented in the textbook and in class, convert the following NFA into an equivalent DFA.