**Theory of Computation (CS 320)**

**Homework #1**

**Due: Sept. 14, 2016**

Instructions:

- Have your written solutions ready at the beginning of class.
- You are allowed – and even encouraged – to work with other students, as well as to use textbooks and resources from the Internet, to solve these problems. However, your write-up must be your own and you must understand your answers. Inability to explain what you have written may result in losing credit for the homework assignment, and is likely to also result in poor performance on the exam.

Maximum score: 50 points

- Recall that a grammar is defined as G = (V, T, S, P) where V is the set of variables, T is the set of terminal (alphabet) symbols, S is the start symbol (one of the variables), and P is the set of production rules. Suppose that a password for a website is comprised of only letters from {a, b, c} and digits from {1, 2, 3} and must contain at least one such letter and one such digit (but in no particular order). Devise a grammar that generates the language of passwords accepted by this website.

- Recall that a deterministic finite automaton (DFA) is defined as (Q, Σ, δ, q
_{0}, F) where Q is the set of states, Σ is the input alphabet, δ is the transition function, q_{0 }is the start state, and F is the set of final (accepting) states. Design a DFA that accepts the language in question 1. (Hint: perhaps use a case-based state design similar to the example discussed in class for a DFA that accepts strings with an even number of 0’s and odd number of 1’s.)

- Last week, we proved that if w
_{1}and w_{2}are words, then (w_{1}w_{2})^{R}= w_{2}^{R }w_{1}^{R}. Prove a similar result for languages, namely that if L_{1}and L_{2}are languages, then (L_{1}L_{2})^{R}= L_{2}^{R }L_{1}^{R}. (Hint: to prove that two languages are equal, you must show that every element of the first language is an elements of the second language, and every element of the second language is an element of the first language.)

- Find grammars for these languages:

- L = {a
^{n}where n is even and n ≥ 0} - L = {a
^{n}where n is odd and n ≥ 1} - L = {a
^{n}where n is even and n ≥ 3}

- Find the respective languages accepted by the following two machines: