Computer Science | Science at Rensselaer
Homework 1 Solution
1. Problem 9 on page 27.
Prove or disprove the following claims:
a) (L1(L2)R = L1R(L2R for all language L1 and L2
First prove all the strings in X = (L1(L2)R are in Y = L1R(L2R. Assume w in X, then wR in L1(L2. If wR in L1 then w in L1R – in Y, same to wR in L2. So any string in X is in Y at the same time.
Second prove all the string in Y are in X. Similar to above.
b) (LR)* = (L*)R for all languages L.
From definition of the * operation we have:
(LR)* = (LR)0 ( (LR)1 ( (LR)2 ( …, and
(L*)R = (L0 ( L1 ( L2 ( …)R.
By applying part (a) of the same problem many times we obtain:
(L*)R = (L0 ( L1 ( L2 ( …)R = (L0)R ( (L1)R ( (L1)R ( …
Therefore, we only need to prove that (LR)k = (Lk)R, for any k ( 0.
Next, we prove by induction that (LR)k = (Lk)R, for any k ( 0. For the induction basis, when k = 0, (LR)k = {(} and (L k) R = {(} and thus (LR)k = (L k) R. For the induction hypothesis, assume when k ( n that (LR)n = (L n) R. For the induction step, when k = n+1,
(L R) n+1 = (L R) n ( LR and (L n+1) R = (L ( Ln)R = (L n) R ( LR. By the induction hypothesis it follows that (LR)n+1=(L n+1) R. Subsequently, the statement holds for any k.
2. Problem 2 on page 45
For ( = {a,b}, construct DFA’s that accept the sets consisting of
a) all strings with exactly one a
b) all strings with at least one a
d) all strings with at least one a and exactly two b’s
e) all the strings with exactly two a’s and more than two b’s
The automaton is constructed with similar techniques as above.
3. Problem 6 on page 45
Give a set notation description of the language accepted by the automation depicted in the following diagram. Can you think of a simple verbal characterization of the language?
L = {w: w(b*a or w ( b*a(a|b)*b}
The language is all the strings with exactly one a or more than one a but end with b.
4. Problem 9 on page 53
a) Find an NFA with three states that accepts the language
L = {an : n(1} ( {bmak : m(0, k(0}
Notice that L = {bmak : m(0, k(0}, since for n=1 and m=0 and k=1
an = bmak. Therefore an automaton with three states is the following.
b) Do you think the language in part (a) can be accepted by an NFA with fewer than three states?
Yes, it can be accepted by an NFA with two states. Simply remove state q2 in the automaton of part (a):
5. Convert the NFA you constructed in Problem 9(a), page 53, to an
equivalent DFA. Show the intermediate steps of the conversion.
Initial state:
Transitions from {q0}:
Transitions from {q1, q2}:
Transitions from {q0, q1, q2}:
Transitions from (:
Final states (final DFA):
-----------------------
q1
q0
q2
a
a
b
b
b
a
{q1, q2}
a
b
a
b
a
b
b
a
b
a
b
b
a
a
b
a
b
b
a
a
a
a
a
a
a
b
b
b
a
b
a
b
(
b
a
{q0}
{q1, q2}
{q0}
{q0, q1, q2}
b
a
{q0}
(
q1
q2
q0
b
(
q1
{q0, q1, q2}
q0
(
a
b
b
a
(
{q1, q2}
{q0, q1, q2}
b
a
{q0}
b
a
a
b
b
a
(
{q1, q2}
{q0, q1, q2}
b
a
{q0}
a, b
a, b
a
b
b
a
(
{q1, q2}
{q0, q1, q2}
b
a
{q0}
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- sets and set notation
- part one set notation and problem solving with venn
- use the following to answer questions 1 26
- chapter 10 math notes
- math 115 highline college
- north tonawanda city schools overview
- computer science science at rensselaer
- lesson plan title
- domain and range worksheet
- white plains public schools overview
Related searches
- igcse computer science workbooks pdf
- igcse computer science workbook
- igcse computer science workbook answer
- igcse computer science coursebook pdf
- computer science people
- what is computer science like
- computer science revision
- igcse computer science revision notes
- college computer science project ideas
- ideas for computer science project
- computer science projects for students
- computer science final project