Automata Forml Lang homework

1. (10 points) Let ∑ = {a, b}. Define the language L = { w | w ∈ ∑* and |w| < 4 }, 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, 2*i) | i ≤ 5 and i ∈ } ⋃ { (i, i-1) | 3 ≤ i ≤ 9 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 0 and has an even number of 1’s }.

7. (15 points) Consider the alphabet For each of the languages below, create a DFA to accept it:

a) L = { w | w contains an odd number of ’s or an odd number of ’s}

b) L = { w | w consists in which every is preceded by two ’s}

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

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| is odd and w ends with a }. 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.