Analysis of Automata, Regular Languages & Computation in CS Theory

This assignment solution delves into the theoretical aspects of computer science, focusing on finite automata, regular languages, and their properties. It addresses key concepts such as non-deterministic finite automata (NFA), their conversion to deterministic finite automata (DFA), and the applicat...Read More

1
Theoretical Aspects of Computer Science

2
Contents
Theoretical Aspects of Computer Science.............................................................................................1
Question 1.............................................................................................................................................3
a.........................................................................................................................................................3
b.........................................................................................................................................................3
c.........................................................................................................................................................3
d.........................................................................................................................................................5
Question 2.............................................................................................................................................6
a.........................................................................................................................................................6
b.........................................................................................................................................................8
Question 3...........................................................................................................................................10
c.......................................................................................................................................................10
Question 4...........................................................................................................................................10
a.......................................................................................................................................................11
b.......................................................................................................................................................11
c.......................................................................................................................................................11
References...........................................................................................................................................12

3
Question 1
a
The given finite automaton is a non-deterministic finite automaton because the transition
from a state is at multiple next states for each input symbol. There are empty string
transitions as well which do not happens in DFA. Apart from this, there is more than one
final state which happens only in NFA (Hopcroft, 2011).
b
The non-deterministic finite automaton is defined by 5 tuples. Let M=(Q, ∑, ,q0,F) and w aẟ
string over ∑ where,
 Q is a finite set of states
 ∑ is a finite alphabet
 : Q * ∑ is the transition functionẟ
 q0 € Q is the start state
 F € Q is the set of accept states
c
Transition table
State(q) Input(a,b) Next State( (q,(a,b)))ẟ
0 a {1,4}

4
1 b {2}
1 a {ᴓ}
2 a {3}
2 b {ᴓ}
3 a {ᴓ}
3 b {1}
4 a {ᴓ}
4 b {5}
5 a {4}
5 b {ᴓ}
The strings which will be accepted are:
1. ∑={abab}
2. ∑={a}
3. ∑={aba}

5
Hence, for a string of length up to 5 over the alphabet none of the strings will be accepted all
will be rejected.
d
A generalized nondeterministic finite automaton (GNFA) is basically a graph in which the
edges are allocated by the regular expressions and the start state is at 0-degree.To convert a
NFA into regular expression using GNFA algorithm, the language has to be converted into a
DFA first (Hollos, 2013).
Hence, the DFA will be,
Steps to get the regular expression are:
Step1: Remove state 5
Step2: Now remove state 2
Step3: At last, remove state 3.

6
Therefore, the regular expression will be a (b a b) *.
Question 2
a
The given NFA is,
Transition table of the given NFA is,
State Input Next State
A(start) 0 B,C
A 1 ᴓ
B(final) 0 D
B 1 B
C(final) 0 ᴓ

7
C 1 A
D 0 ᴓ
D 1 A
To convert this NFA into a DFA using subset construction method following steps are taken,
Eclosure(0)={A}
Eclosure(move(A,0))={B,C}=4
Eclosure(move(A,1))={ᴓ}
Eclosure(move(B,0))={D}=3
Eclosure(move(B,1))={B}=1
Eclosure(move(C,0))={ᴓ}
Eclosure(move(C,1))={A}=0
Eclosure(move(D,0))={C}=2
Eclosure(move(D,1))={A}=0
Eclosure(move([B,C],0)={D}=3
Eclosure(move([B,C],1)={B,D,A}=5
Eclosure(move([B,D,A],0)={[B,C,D]}=6
Eclosure(move([B,D,A],1)={[B,D,A]}=5
Eclosure(move([B,C,D],0)={[D,C]}=7
Eclosure(move([B,C,D],1)={[B,D,A]}=5
Eclosure(move([D,C],0)={[C]}=2
Eclosure(move([D,C],1)={[A]}=0
Transition table of the DFA will be,
State Input Next state
0 0 4
0 1 ᴓ
1 0 3
1 1 1
2 0 ᴓ
2 1 0

8
3 0 2
3 1 0
4 0 3
4 1 5
5 0 6
5 1 5
6 0 7
6 1 5
7 0 2
7 1 0
The DFA will be,
b
1.
Suppose that A1 is a regular language. Let p be the “pumping length” of the Pumping
Lemma. Consider the string s = apbapbapb. Note that s ∈ A1 since s = (ap b)3 , and |s| = 3(p +
1) ≥ p, so the Pumping Lemma will hold. Thus, we can split the string s into 3 parts s = xyz
satisfying the conditions i. xyi z ∈ A1 for each i ≥ 0,
ii. |y| > 0,

9
iii. |xy| ≤ p.
Since the first p symbols of s are all a’s, the third condition implies that x and y consist only
of a’s. So z will be the rest of the first set of a’s, followed by bap bapb. The second condition
states that |y| > 0, so y has at least one a. More precisely, we can then say that
x = aj for some j ≥ 0,
y = ak for some k ≥ 1,
z = am bap bap b for some m ≥ 0.
Since ap bap bap b = s = xyz = aj ak am bap bap b = aj+k+m bap bap b, we must have that j + k + m
= p. The first condition implies that xy2 z ∈ A1, but
Xy2 z = aj ak ak am bap bap b
= ap+k bap bap b
Since j + k + m = p. Hence, xy2 z € A 1 because k ≥ 1, and we get a contradiction. Therefore,
A1 is a non-regular language (Sane, 2007).
2. A2 = { w ∈ {a, b} ∗ | w = wR }.
Suppose that A2 is a regular language. Let p be the “pumping length” of the Pumping
Lemma. Consider the string s = ap bap. Note that s ∈ A2 since s = sR , and |s| = 2p + 1 ≥ p, so
the Pumping Lemma will hold. Thus, we can split the string s into 3 parts s = xyz satisfying
the conditions
i. xyi z ∈ A2 for each i ≥ 0,
ii. |y| > 0,
iii. |xy| ≤ p.
Since the first p symbols of s are all a’s, the third condition implies that x and y consist only
of a’s. So z will be the rest of the first set of a’s, followed by bap. The second condition states
that |y| > 0, so y has at least one a. More precisely, we can then say that
x = aj for some j ≥ 0,
y = ak for some k ≥ 1,

10
z = am bap for some m ≥ 0.
Since ap bap = s = xyz = aj ak am bap = aj+k+m bap , we must have that j + k + m = p. The first
condition implies that xy2 z ∈ A2, but
Xy2 z = aj ak ak am bap
= ap+k bap
Since j + k + m = p. Hence, xy2 z € A2 because (ap+k bap)R = aP bap+k≠ ap+k bap since k ≥ 1, and
we get a contradiction. Therefore, A2 is a non-regular language (Kallmeyer, 2010).
Question 3
c
The NFA that will determine whether any binary numbers (presented as a string) is divisible
by 3 is described in the below figure.
The general idea of how such a finite automaton can be constructed to determine the
divisibility of an integer n is construct the number of states in accordance to the
integer. And then construct a regular expression of it and hence make a transition
diagram (Dediu, 2016).
Question 4
The PDA of the language L1 will be

11
a.
a
The idea is that the left part will always count the number of aa’s. And every time it will
see 2 a, it will be pushed to 3 b into the stack. Similarly, on the right hand side, every time
it will see 4 a’s it will be pushed to b into the stack.
b
The diagram is described above.
L2= { w|w=an bn cn forn=0,1,2, … }
It is easy to determine PDA of the following language. The PDA will accept the
strings of the form anbicj where i+j=2n and i,j>0. For example, the string “aabbcc” is
accepted.
L3= { w|w=an b3 n c2 m dm forn ,m=0,1,2, … }
It is not possible to create a PDA of the given language because every time 3 integers
will be pushed on it will again repeat. And the given language is not a context free
language (Czumaj, 2012).
c
The grammar of the given transition diagram will be,

12
V= {A, B, C}
T= {0, 1}
S= {A}
P=
(A)= 0(B)
(A)= 1(C)
(B)=μ
(B)=0(A)
(C)=μ
(C)=0(B)
(C)=1(A)
References
Czumaj, A. (2012). Automata, languages, and programming. Heidelberg: Springer.
Dediu, A., Janoušek, J., Martín-Vide, C. and Truthe, B. (2016). Language and Automata Theory
and Applications. Cham: Springer International Publishing.
Hollos, S. and Hollos, J. (2013). Finite automata and regular expressions. Longmont (CO):
Abrazol.
Hopcroft, J., Motwani, R. and Ullman, J. (2011). Introduction to automata theory, languages, and
computation. Delhi: Pearson Education.
Kallmeyer, L. (2010). Parsing beyond context-free grammars. Heidelberg: Springer.
Sane, S. (2007). Theory of computer science. Pune, India: Technical Publications Pune.