Lehman College, City University of New York

Fall 2016

Due Dates: Oral presentations of material begin on 22 November.

Written descriptions of material presented due one week after presentation.

Written descriptions of material presented due one week after presentation.

An integral part of this class is understanding and presenting the problems assigned as homework. Everyone is expected to do all the problems, but we will take turns on who presents the problem solutions to the class (every 2-3 weeks, depending on the number of students in the class). Within a week of presenting a problem solution to the class, you must submit a written description of it, via the Blackboard system. The written solutions will be posted on the Blackboard website for the class, so, they can used by everyone to study for the exams. Since it's hard to write down answers that are concise and are easily readable by all, if you wish to improve a grade on any problem, you may resubmit it for grading.

- Answer the following for the DFA, M. Explain your answers.

- Is <M, aacc> ∈ A
_{DFA}? - Is <M, aac> ∈ A
_{DFA}? - Is <M> ∈ A
_{DFA}?

- Is <M, aacc> ∈ A
- Answer the following for the DFA, M. Explain your answers.

- Is <M, acac> ∈ A
_{DFA}? - Is <M, acac> ∈ A
_{REX}? - Is <M,M> ∈ EQ
_{DFA}?

- Is <M, acac> ∈ A
- Answer the following for the DFA, M. Explain your answers.

- Is <M, aacc> ∈ A
_{DFA}? - Is <M, aac> ∈ A
_{DFA}? - Is <M> ∈ E
_{DFA}?

- Is <M, aacc> ∈ A
- Answer the following for the DFA, M
_{1}and M_{2}. Explain your answers.M _{1}:M _{2}:- Is <M
_{1}, abb> ∈ A_{DFA}? - Is <M
_{2}, abb> ∈ A_{DFA}? - Is <M
_{1},M_{2}> ∈ EQ_{DFA}?

- Is <M
- Let:
ALL

Show that ALL_{DFA}= {<A> | A is a DFA that recognizes Σ*}_{DFA}is decidable (assume that the alphabet is {0,1}). - Let:
Aε

Show that Aε_{CFG}= {<G> | G is a CFG that generates ε}_{CFG}is decidable (assume that the alphabet is {0,1}).

- Consider the problem of testing whether a DFA and a regular expression are equivalent. Express the problem as a language and show that it is decidable.
- Let
A = {<R,S> | R and S are regular expressions and L(R) ⊆ L(S)}

Show that A is decidable (assume that the alphabet is {0,1}).