Theory of Computation

Desklib is an online library that provides study material for Theory of Computation. Find solved assignments, essays, and dissertations on various topics related to Theory of Computation. Get comprehensive study resources for your course.

Running head: THEORY OF COMPUTATION
Theory of computation
Name of the Student
Name of the University
Author’s Note

1
0
q0 q1 q2
0
1
0 1
1
THEORY OF COMPUTATION
Answer to Question 1: (Deterministic Finite Accepters)
Problem 1:
0001, 01001 are accepted by the dfa
Problem 2:
For For  = {a, b} construct dfa’s that accepts the sets consisting of
a. all strings with exactly one a
b. all strings with at least one a

2
a a a a
b b a,b
b
b
q0 q1 q2 q3 q4+
THEORY OF COMPUTATION
c. all strings with no more than 3 a’s
d. all strings with at least one a and exactly two b’s

3
THEORY OF COMPUTATION
e. all strings with exactly two a’s and more than two b’s
Problem 3:
Show that if we change fig 2.6 making q3 a nonfinal state and making q0,q1, q2 final states the
resulting dfa accepts
For any dfa the statement is true. If the final and the non-final states are switched then any of the
string leaving in an accepting state leaves the non-final state because we have switched around

4
THEORY OF COMPUTATION
the different final states. Thus by definition the language that is accepted by the new machine
acts as the compliment of language accepted by original one.
Problem 4:
Generalize the observation in the previous exercise. Specifically, show that if M=Q,∑,∂,q0,F and
It is proved by contradiction suppose M is not a minimal DFA for X then there exists another
DFD Z for A such that Z has fewer states than M. Another DFD Z’ is created by swapping the
acceptance and non-acceptance states of Z. The Z’ recognizes the complement of X. But the
complement of X is just X’ so Z’ recognizes X. Z’has the same number of states as Z and M has
same number of states as M. Thus if it is assumed that Z has strictly fewer states than M then Z’
has strictly fewer states than M, then Z’would have strictly fewer states than M. But since Z’
recognizes X, this contradicts our assumption that M is minimal DFA for X. Therefore M is a
minimal DAA for X.
Problem 5:
a. Dfa for the languages L= {ab5wb2 : w  {a, b}*}
b. Dfa for the languages L = { abnam : n ≥ 2, m ≥ 3}

5
THEORY OF COMPUTATION
c. Dfa for the languages L= {w1abw2 : w1  {a, b}*, w2  {a, b}*}
d. Dfa for the languages L= {ban:n ≥1,n≠5}
Problem 9:
Consider the sets of strings on {0, 1} defined by the requirements below. Construct dfa’s.
a. Every 00 is followed immediately by a 1

6
1 0 0
1
0 0,1
1
1 0 0
0
0
1 0
0
1
1
0 0
1
1
0
1
0
THEORY OF COMPUTATION
b. all strings containing 00 but not 000
c. The leftmost symbol differs from the rightmost
d. Every substring of four symbols has at most two 0’s

7
THEORY OF COMPUTATION
f. All strings in which the leftmost two symbols and the rightmost two
symbols are identical.
g. All strings of length four or greater in which the leftmost 3 symbols are the
same, but different from the rightmost symbol.

8
THEORY OF COMPUTATION
Answer to Question 2: (Non Deterministic Finite Accepters)
Problem 1:
Provide in details the claim made in the previous section that if in a transition graph there is a
walk labeled w, there must be some walk labeled w of length no more than Λ + (1 + Λ) |w|
If between two vertices vi and vj there is any walk labeled w, then there must be some
walk labeled w of length no more than Λ + (1 + Λ)|w|, where Λ is the number of λ-edges in the
graph.
⇒ Computing δ ∗ (vi , w): evaluate all walks of length at most Λ + (1 + Λ)|w| originating at
some vi .
Problem 2:
Find a dfa that accepts the language defined by the nfa

9
THEORY OF COMPUTATION
Here the language accepted by NFA is aaa+(aa)*
Problem 3:
Find a dfa that accepts the complement of the language defined by the nfa
Now the complement of language is epsilon + a + aaa(aa)*
Problem 9:
Do you think Exercise 8 can eb solved 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):

10
THEORY OF COMPUTATION
Answer to Question 3
Problem 1
Initial state:
Transitions from {q0}:
Transitions from {q1, q2}:
Transitions from {q0, q1, q2}:
{q0}
{q0}
a
b
{q0, q1, q2}
{q1, q2}
{q0}
a
b
{q0, q1, q2}
{q1, q2}

a
b

11
THEORY OF COMPUTATION
Transition from :
Final states (final DFA):

12
THEORY OF COMPUTATION
Problem 2
Convert the nfa in Exercise 12, Section 2.2. into an equivalent dfa
Following is the procedure of converting an nfa to a dfa, we have
{q0}  F since λ  L(M);
{q1; q2}; {q0; q1; q2}  F since q1 is a final state in M.
Thus, the result dfa is shown below

13
THEORY OF COMPUTATION
Problem 3:
Convert the following nfa into an equivalent dfa
Following is the procedure of converting an nfa to a dfa, we have
{q0}  F since λ  L(M);
{q1; q2}; {q0; q1; q2}  F since q1 is a final state in M.
Thus, the result dfa is shown below

14
THEORY OF COMPUTATION
Problem 8:
Find an nfa without λ-transition and with a single final state that accepts the set {a}∪{bn:n≥1}
Since L is regular there exists a dfa, D = (Q, Σ, δ, q0, F), with an associated transition graph, GD,
such that L(D) = L. We will construct an nfa N = (Q ∪ {qf }, Σ, δ0 , q0, {qf }) where qf ∈/ Q by
giving its transition graph GN as follows:
1. From GD, remove the final label from every final state (making them nonfinal states).
2. Add a new state qf and label it as a final state.
3. For every state qi , if there is a transition from qi to a state in F on input a ∈ Σ, then add a
transition from qi to qf on input a.
Clearly, N has a single accept state, qf , and no λ-transitions (since D is a dfa and we did not add
any λ-transitions in our construction of N). We will now show that L(N) = L. First note that since
λ /∈ L, every w ∈ L can be written as w = va for some v ∈ Σ ∗ and an a ∈ Σ.

15
THEORY OF COMPUTATION
Now, w = va ∈ L iff there is a walk on GD labeled with w from q0 to qi with qi ∈ F iff there is a
walk on GD labeled with v from q0 to qj and a transition from qj to qi on input a iff there is a
walk on GN labeled with v from q0 to qj and a transition from qj to qf on input a (since every
transition in GD is a transition in GN and from step (3) in the construction of GN ) iff there is a
walk on GN labeled with w from q0 to qf
iff w ∈ L(N).
Thus, w ∈ L iff w ∈ L(N). Therefore we conclude that L(N) = L and that for any regular
language that does not contain λ, there exists an nfa without λ-transitions and with a single final
state that accept L.
Problem 9:
Since L is a regular language, we can construct a corresponding dfa, N, such that L(N) = L (For
every regular language, there is a corresponding dfa, by definition, and for every dfa, there is an
equivalent nfa).
By definition, L R consists of all strings in language L in reverse order. We will construct a nfa,
NR, representing L R such that L(NR) = L R. NR will contain an additional start state with λ-
transitions to the final states of N. The direction of every transition in N is reversed. Also, the
start state of N will be the final state of NR. The construction of nfa NR is as follows:
Let N = (Q, Σ, δ, qn, F)
NR = (Q ∪ {q0}, Σ, δr, qr, {qn})
Set of states of NR = set of states of N along with q0 = Q ∪ {qr}
Σ = alphabet of NR = same as N

16
THEORY OF COMPUTATION
qr = start state of NR
{qn} = set of final states of NR = start state of N
Transition function:
δr(q, a) = {q1 : δ(q1, a) = q}
δr(qr, λ) = F
Answer to Question 4:
Problem 1:
Minimize the number of states in the dfa in Figure 2.16
After following marking the distinguishable states, we will end up to 3 sets of indistinguishable
states as:{{q1, q2}, {q1}} , {{q0, q1, q2}, {q0, q1}} , {{∅}, {q2}}. Therefore, the final DFA
would be as follows:
Problem 2:
Find minimal dfa for the following language:
a. L ={anbm>:n≥2,m≥1}

17
THEORY OF COMPUTATION
b. L={anb : n ≥ 0}∪ {bna : n ≥ 1}
We first construct a nfa that accepts the language L. Then, we use the algorithm described in
Theorem 2.2 to convert the nfa to dfa. Finally, we follow the steps in Theorem 2.3 to minimize
the dfa.
The following is the corresponding nfa

18
THEORY OF COMPUTATION
The following is the corresponding dfa
Minimized dfa
c. L={an:n≥0,n  3}
L={anbn∣n≥0,n≠3}L={anbn∣n≥0,n≠3}
Consider the following Languages:

19
THEORY OF COMPUTATION
L1={anbn∣n≥0}L1={anbn∣n≥0}
L2=Σ∗−a3b3L2=Σ∗−a3b3
We can see that
 L1L1 is a Deterministic Context Free Language (DCFLDCFL)
 L2L2 is a Regular Language (RLRL)
 L=L1∩L2
d. L = {an: n  2, n  4}

20
THEORY OF COMPUTATION
e. L= {an:n mod 3 = 0}∪{an: mod 5 =1}
step 1: n mod 3 = 0
put n = 0 ==> 0 mod 3 = 0
==>a^0 = ∈
step 2 : n mod 5 = 1
put n = 2 ==> 2 mod 5 = 1
==>a^2="aa"
L=(a^0) U (a^2) ==>(∈) U ("aa")
so that "aa" is the minimum string accept by the language and the DFA is
given below

21
THEORY OF COMPUTATION

22
THEORY OF COMPUTATION
Bibliography
(2019). Almuhammadi.com. Retrieved 21 April 2019, from
http://almuhammadi.com/sultan/books/Linz.5ed.pdf
D’antoni, L., & Veanes, M. (2015). Extended symbolic finite automata and transducers. Formal
Methods in System Design, 47(1), 93-119.
D’Antoni, L., & Veanes, M. (2017, April). Forward bisimulations for nondeterministic symbolic
finite automata. In International Conference on Tools and Algorithms for the
Construction and Analysis of Systems (pp. 518-534). Springer, Berlin, Heidelberg.
Gruska, J., Qiu, D., & Zheng, S. (2015). Potential of quantum finite automata with exact
acceptance. International Journal of Foundations of Computer Science, 26(03), 381-398.
Holzer, M., Jakobi, S., & Kutrib, M. (2018). Minimal reversible deterministic finite
automata. International Journal of Foundations of Computer Science, 29(02), 251-270.
Jančić, Z., Micić, I., Ignjatović, J., & Ćirić, M. (2016). Further improvements of determinization
methods for fuzzy finite automata. Fuzzy Sets and Systems, 301, 79-102.
Zhang, K., Zhang, L., & Xie, L. (2016). Finite automata approach to observability of switched
Boolean control networks. Nonlinear Analysis: Hybrid Systems, 19, 186-197.
Zheng, S., Li, L., Qiu, D., & Gruska, J. (2017). Promise problems solved by quantum and
classical finite automata. Theoretical Computer Science, 666, 48-64.