EXPERIMENT NO: 1
Aim / Title: Program to build DFA that starts with ‘a’ and end with ‘a’ for input (a, b)
Problem Statement: DFA (Deterministic Finite Automaton or Acceptor) is a finite state machine that
accepts or rejects strings of symbols. DFA accepts the string if it reaches the final state and rejects
otherwise.
Now the problem is, provided a string as input character by character and we have to check whether the
string starts and ends with ‘a’. We can only store the current character, since there is no concept of
memory and hence the DFA cannot store the string provided. Otherwise, we could have just checked the
first and last character for this problem. The input set for this problem is (a, b).
Objectives: Solve using DFA concepts
Outcomes:
String ababb starts with 'a' but doesn't end with 'b'. Should not be accepted by DFA
String ababba starts with 'a' and ends with 'a'. Should be accepted by DFA
● Hardware requirements: Processor – Intel Xeon E2630 v4 – 10 core processor, 1.2 GHz with
Turboboost upto 3.1 GHz. ...
● Motherboard – ASRock EPC612D8A.
● RAM – 1 GB DDR2 2133 MHz.
● 80 GB Hard Disk (7200 RPM) + 512 GB SSD etc.
● GPU – NVidia TitanX Pascal (12 GB VRAM)
Software requirements: JFLAP Simulator.
Output: Converted given problem in DFA using JFLAP and in a program using java
Theory: We first built a DFA for this problem. Making DFA is like making a flowchart for this program
and then implement it in any language. You should have the knowledge of DFA and Finite Automata.
The DFA for given problem is:
1 | Page
Program:
// Java Program to DFA that accept strings which starts and end with 'a' over input(a, b)
import [Link];
class StartWithAandEndWithA
{
public static void main(String[] args)
{
Scanner sc = new Scanner([Link]);
[Link]("Enter a string must contains a's and b's only :");
String str=[Link]();
int q=0;
for(char c : [Link]())
{
switch(q)
{
case 0 : q=(c=='a')?1:2;
break;
case 1: q=(c=='a')?1:3;
break;
case 2: q=(c=='a'||c=='b')?2:2;
break;
case 3 : q=(c=='a')?1:((c=='b')?3:1);
}
}
if(q==1)
[Link](str + " String start with a and ends with a ");
else
[Link](str + " String doen't start with a or ends with a ");
}
}
Instructions:1) Input : ababa
Output : ababa String start with a and ends with a
2)Input : ababb
Output : ababb String doesn’t start with a or ends with b
Roll No. Name of Date of Date of Grade Sign of Sign of
Student Performance Evaluation Student Faculty
2 | Page
EXPERIMENT NO: 2
Aim / Title: Design a Program for creating machine that accepts three consecutive one over {0,1}
Problem Statement: DFA (Deterministic Finite Automaton or Acceptor) is a finite state machine that
accepts or rejects strings of symbols. DFA accepts the string if it reaches the final state and rejects
otherwise.
Now the problem is, provided a string as input character by character and we have to check whether the
string having three consecutive 1’s or not.
Objectives: Solve the given problem using DFA concepts
Outcomes: 001110101 should be accepted by DFA because it contains three consecutive 1’s
00110101 should not be accepted by DFA because it doesn’t contains three consecutive 1’s
● Hardware requirements: Processor – Intel Xeon E2630 v4 – 10 core processor, 1.2 GHz with
Turboboost upto 3.1 GHz. ...
● Motherboard – ASRock EPC612D8A.
● RAM – 1 GB DDR2 2133 MHz.
● 80 GB Hard Disk (7200 RPM) + 512 GB SSD etc.
● GPU – NVidia TitanX Pascal (12 GB VRAM)
Software requirements: JFLAP Simulator.
Output: Converted in DFA
Theory: We first built a DFA for this problem. Making DFA is like making a flowchart for this program
and then implement it in any language. You should have the knowledge of DFA and Finite Automata.
The DFA for given problem is:
3 | Page
Program:
// Java Program to Program for creating machine that accepts three consecutive one over {0,1}
import [Link];
class ThreeConsecutiveOnes
{
public static void main(String[] args)
{
Scanner sc = new Scanner([Link]);
[Link]("Enter a string must contains 1's and 0's only :");
String str=[Link]();
int q=0;
for(char c : [Link]())
{
switch(q)
{
case 0 : q=(c=='0')?0:((c=='1')?1:0);
break;
case 1: q=(c=='0')?0:((c=='1')?2:0);
break;
case 2: q=(c=='0')?0:((c=='1')?3:0);
break;
case 3 : q=(c=='0'||c=='1')?3:3 ;
}
}
if(q==3)
[Link](str + " acceptd contains three consecutive 1's ");
else
[Link](str + " not acceptd, does not contains three consecutive 1's ");
}
}
Instructions: Input : 001110101
Output : acceptd contains three consecutive 1's
Input : 00110101
Output : not acceptd, does not contains three consecutive 1's
Roll No. Name of Date of Date of Grade Sign of Sign of
Student Performance Evaluation Student Faculty
4 | Page
EXPERIMENT NO: 3
Aim / Title: Design a Program for creating machine that accepts the string always ending with 101
Problem Statement: DFA (Deterministic Finite Automaton or Acceptor) is a finite state machine that
accepts or rejects strings of symbols. DFA accepts the string if it reaches the final state and rejects
otherwise.
Now the problem is, provided a string as input character by character and we have to check whether the
string ending with 101.
Objectives: Solve the given problem using DFA concepts
Outcomes: 001110101 should be accepted by DFA because it it ends with 101
001101011 should not be accepted by DFA because it doesn’t ends with 101
● Hardware requirements: Processor – Intel Xeon E2630 v4 – 10 core processor, 1.2 GHz with
Turboboost upto 3.1 GHz. ...
● Motherboard – ASRock EPC612D8A.
● RAM – 1 GB DDR2 2133 MHz.
● 80 GB Hard Disk (7200 RPM) + 512 GB SSD etc.
● GPU – NVidia TitanX Pascal (12 GB VRAM)
Software requirements: JFLAP Simulator.
Output: Converted in DFA
Theory: We first built a DFA for this problem. Making DFA is like making a flowchart for this program
and then implement it in any language. You should have the knowledge of DFA and Finite Automata.
The DFA for given problem is:
5 | Page
Program:
// Java Program for creating machine that accepts the string always ending with 101
import [Link];
class EndsWith101
{
public static void main(String[] args)
{
Scanner sc = new Scanner([Link]);
[Link]("Enter a string must contains 1's and 0's only :");
String str=[Link]();
int q=0;
for(char c : [Link]())
{
switch(q)
{
case 0 : q=(c=='0')?0:((c=='1')?1:0);
break;
case 1: q=(c=='0')?2:((c=='1')?1:1);
break;
case 2: q=(c=='0')?0:((c=='1')?3:0);
break;
case 3 : q=(c=='0'||c=='1')?4:4 ;
break;
case 4: q=(c=='0'||c=='1')?4:4 ;
break;
}
}
if(q==3)
[Link](str + " acceptd string ends with 101 ");
else
[Link](str + " not acceptd,string does not ends with 101 ");
}
}
Instructions: Input : 001110101
Output : acceptd contains string ends with 101
Input : 001101011
Output : not acceptd, does not ends with 101
Roll No. Name of Date of Date of Grade Sign of Sign of
Student Performance Evaluation Student Faculty
6 | Page
EXPERIMENT NO: 4
Aim / Title: Design a Program for Mode 3 Machine
Problem Statement: DFA (Deterministic Finite Automaton or Acceptor) is a finite state machine that
accepts or rejects strings of symbols. DFA accepts the string if it reaches the final state and rejects
otherwise.
Now the problem is, provided a string as input character by character and we have to check whether the
binary number is divisibel by 3 or not.
Objectives: Solve the given problem using DFA concepts
Outcomes: 11,110,1001 should be accepted by DFA because it is divisble by 3
10,1000 should not be accepted by DFA because it is not divisible by 3
● Hardware requirements: Processor – Intel Xeon E2630 v4 – 10 core processor, 1.2 GHz with
Turboboost upto 3.1 GHz. ...
● Motherboard – ASRock EPC612D8A.
● RAM – 1 GB DDR2 2133 MHz.
● 80 GB Hard Disk (7200 RPM) + 512 GB SSD etc.
● GPU – NVidia TitanX Pascal (12 GB VRAM)
Software requirements: JFLAP Simulator.
Output: Converted in DFA
Theory: We first built a DFA for this problem. Making DFA is like making a flowchart for this program
and then implement it in any language. You should have the knowledge of DFA and Finite Automata.
The DFA for given problem is:
7 | Page
Program:
// Java Program for creating machine that accepts the binary string divisible by 3
import [Link];
class BinaryModThree
{
public static void main(String[] args)
{
Scanner sc = new Scanner([Link]);
[Link]("Enter a Binary string :");
String str=[Link]();
int q=0;
for(char c : [Link]())
{
switch(q)
{
case 0 : q=(c=='0')?0:1; break;
case 1: q=(c=='1')?0:2 ;
break;
case 2: q=(c=='0')?1:2;
}
}
if(q==0)
[Link](str + " binary number divisible by 3 ");
else
[Link](str + " binary number not divisible by 3 ");
}
}
Instructions: Input : 1001
Output :1001 binary number divisible by 3
Input : 1000
Output :1000 binary number not divisible by 3
Roll No. Name of Date of Date of Grade Sign of Sign of
Student Performance Evaluation Student Faculty
8 | Page
EXPERIMENT NO: 5
Aim / Title: Design a program for accepting decimal number divisible by 2
Problem Statement: DFA (Deterministic Finite Automaton or Acceptor) is a finite state machine that
accepts or rejects strings of symbols. DFA accepts the string if it reaches the final state and rejects
otherwise.
Now the problem is, provided a string as input character by character and we have to check whether the
decimal number is divisibel by 2 or not.
Objectives: Solve the given problem using DFA concepts
Outcomes: 2,12,800 should be accepted by DFA because it is divisble by 2
3,31,801 should not be accepted by DFA because it is not divisible by 2
● Hardware requirements: Processor – Intel Xeon E2630 v4 – 10 core processor, 1.2 GHz with
Turboboost upto 3.1 GHz. ...
● Motherboard – ASRock EPC612D8A.
● RAM – 1 GB DDR2 2133 MHz.
● 80 GB Hard Disk (7200 RPM) + 512 GB SSD etc.
● GPU – NVidia TitanX Pascal (12 GB VRAM)
Software requirements: JFLAP Simulator.
Output: Converted in DFA
Theory: We first built a DFA for this problem. Making DFA is like making a flowchart for this program
and then implement it in any language. You should have the knowledge of DFA and Finite Automata.
The DFA for given problem is:
9 | Page
Program:
// Java program for accepting decimal number divisible by 2
import [Link];
class DecimalNumberDivisiblebyTwo
{
public static void main(String[] args)
{
Scanner sc = new Scanner([Link]);
[Link]("Enter a integer number :");
int num=[Link]();
String str=[Link](num);
int q=0;
for(char c : [Link]())
{
switch(q)
{
case 0 : q=(c=='0'||c=='2'||c=='4'||c=='6'||c=='8')?0:1;
break;
case 1: q=(c=='1'||c=='3'||c=='5'||c=='7'||c=='9')?1:0; ;
break;
}
}
if(q==0)
[Link](str + " Decimal Number divisible by 2 ");
else
[Link](str + " Decimal Number Not divisible by 2 ");
}
}
Instructions: Input : 800
Output :800 decimal number divisible by 2
Input : 801
Output :801 decimal number not divisible by 3
Roll No. Name of Date of Date of Grade Sign of Sign of
Student Performance Evaluation Student Faculty
10 | Page
EXPERIMENT NO: 6
Aim / Title: Design a program for creating a machine which accepts string having equal no. of 1’s
and 0’s.
Problem Statement: DFA (Deterministic Finite Automaton or Acceptor) is a finite state machine that
accepts or rejects strings of symbols. DFA accepts the string if it reaches the final state and rejects
otherwise.
Now the problem is, provided a string as input character by character and we have to check whether the
string have equal no of 1’s and 0’s.
Objectives: Solve the given problem using DFA concepts
Outcomes: 1001 should be accepted by DFA because it is having equal number of 0’s and 1’s
1101 should not be accepted by DFA because it is not having equal number of 0’s and 1’s
● Hardware requirements: Processor – Intel Xeon E2630 v4 – 10 core processor, 1.2 GHz with
Turboboost upto 3.1 GHz. ...
● Motherboard – ASRock EPC612D8A.
● RAM – 1 GB DDR2 2133 MHz.
● 80 GB Hard Disk (7200 RPM) + 512 GB SSD etc.
● GPU – NVidia TitanX Pascal (12 GB VRAM)
Software requirements: JFLAP Simulator.
Output: Converted in DFA
Theory: We first built a DFA for this problem. Making DFA is like making a flowchart for this program
and then implement it in any language. You should have the knowledge of DFA and Finite Automata.
The DFA for given problem is:
11 | Page
Program:
// Java program for accepting decimal number divisible by 2
import [Link];
class EqualNoOfZerosAndOnes
{
public static void main(String[] args)
{
Scanner sc = new Scanner([Link]);
[Link]("Enter a binary number :");
String str=[Link]();
int q=0;
for(char c : [Link]())
{
switch(q)
{
case 0 : q=(c=='0')?1:3;
break;
case 1: q=(c=='0')?2:0;
break;
case 2: q=(c=='0')?3:1;
break;
case 3: q=(c=='0')?0:2;
break;
}
}
if(q==0)
[Link](str + " have equal number of zero's and one's ");
else
[Link](str + " have unequal number of zero's and one's ");
}
}
Instructions: Input : 1010
Output :1010 have equal number of zero's and one's
Input : 1101
Output : 1101 have unequal number of zero's and one's
Roll No. Name of Date of Date of Grade Sign of Sign of
Student Performance Evaluation Student Faculty
12 | Page
EXPERIMENT NO: 7
Aim / Title: Program to find 2’s complement
Problem Statement: It is the mathematical operation on binary numbers. It is used for computation as a
method of signed number representation. Its complement with respect to 2N defines the two’s
complement an N-bit number.
.
Objectives: Solve the given problem using DFA with output i.e. using Mealy Machine concepts.
Moore and Mealy Machines are Transducers that help in producing outputs based on the input of the
current state or previous state.
Mealy machines are also finite state machines with output value and their output depends on the present
state and current input symbol. It can be defined as (Q, q0, ∑, O, δ, λ’) where:
Q is a finite set of states.
q0 is the initial state.
∑ is the input alphabet.
O is the output alphabet.
δ is the transition function which maps Q×∑ → Q.
‘λ’ is the output function that maps Q×∑→ O.
Outcomes: 101000 should be accepted by Mealy Machine and as a transducer it should give output
011000
Solution :
First calculate 1’s complement of binary number, convert 1 to 0 and 0 to 1 and then add 1 to it. For
example, if binary number is 1011 then its 1’s complement is 0100 and its 2’s complement is 0101
Design mealy machine :
1. Take initial state q0. If there are n number of zeros at initial state, it will remain at initial state.
2. Whenever first input 1 is found then it gives output 1 and go to state q1.
3. After changing a condition we reverse the output . In state q1, if input is zero, output will be 1. And if
input is 1 then output will be 0.
Hardware requirements: Processor – Intel Xeon E2630 v4 – 10 core processor, 1.2 GHz with
Turboboost upto 3.1 GHz. ...
● Motherboard – ASRock EPC612D8A.
● RAM – 1 GB DDR2 2133 MHz.
● 80 GB Hard Disk (7200 RPM) + 512 GB SSD etc.
● GPU – NVidia TitanX Pascal (12 GB VRAM)
13 | Page
Software requirements: JFLAP Simulator.
Output: Converted in Mealy Machine
Theory: We first built a Mealy Machine for this problem. Making Mealy Machine is like making a
flowchart for this problem and then implement it in any language. You should have the knowledge of
Mealy Machine and Moore Machine.
The Mealy Machine for given problem is:
Program:
// Java program for 2’s complement using the concepts of Mealy Machine
class MealyMachine2Complement
{
public static void main(String[] args)
{
Scanner sc = new Scanner([Link]);
[Link]("Enter a binary number :");
String str=[Link]();
char[] str1=[Link]();
char[] str2=new char[[Link]];
int j=[Link]-1;
int q=0;
for(;j>=0;j--)
{
switch(q)
{
case 0 : if(str1[j]=='0')
{
str2[j]='0';
q=0;
}
else
if(q==0 && str1[j]=='1')
{
14 | Page
str2[j]='1';
q=1;
}
break;
case 1: if(str1[j]=='0')
{
str2[j]='1';
q=1;
}
else
if(q==1 && str1[j]=='1')
{
str2[j]='0';
q=1;
}
}
}
for(char c : str2)
[Link](c);
}
}
Instructions: Input : 001
Output :111
Input : 1101
Output : 0011
Roll No. Name of Date of Date of Grade Sign of Sign of
Student Performance Evaluation Student Faculty
15 | Page
EXPERIMENT NO: 8
Aim / Title: Design a Program which will increment the given binary number by 1
Problem Statement: It is the mathematical operation on binary numbers. Increment by 1 means adding
1 to the binary [Link] are two cases in increment by 1 operation
.
Objectives: Solve the given problem using DFA with output i.e. using Mealy Machine concepts.
Moore and Mealy Machines are Transducers that help in producing outputs based on the input of the
current state or previous state.
Transducers in Finite Automata(FA) means FA with [Link] are two types of Machines for FA
with Output.
1. Mealy Machine :
It is FA in which output is associated with each transition. (that means output depends on state and
input).
2. Moore Machine :
It is FA in which output is associated with each state. (that means output depends on state only).
By using these machines, we can design finite automata for various operations like :-
1’s Complement.
2’s Complement.
Binary Full adder.
Increment by 1.
Change the sign bit.
Integer Divisibility Tester.
Logical functions (XOR, OR, AND, NOT).
Sum of present bit & previous bit etc.
16 | Page
Outcomes: 101000 should be accepted by Mealy Machine and as a transducer it should give output
101001
Solution of given problem:
There are two cases in increment by 1 operation
On combining both cases, we got the algorithm that, until first 0 comes, makes all 1⇢ 0 and when 0
comes makes it 1, then the remaining part of the output is the same as the input. Here, inputs are taken
from LSB.
Hardware requirements: Processor – Intel Xeon E2630 v4 – 10 core processor, 1.2 GHz with
Turboboost upto 3.1 GHz. ...
● Motherboard – ASRock EPC612D8A.
● RAM – 1 GB DDR2 2133 MHz.
● 80 GB Hard Disk (7200 RPM) + 512 GB SSD etc.
● GPU – NVidia TitanX Pascal (12 GB VRAM)
Software requirements: JFLAP Simulator.
Output: Converted in Mealy Machine
Theory: We first built a Mealy Machine for this problem. Making Mealy Machine is like making a
flowchart for this problem and then implement it in any language. You should have the knowledge of
Mealy Machine and Moore Machine.
The Mealy Machine for given problem is:
17 | Page
Program:
// Java program for increment the given binary number by 1
import [Link];
class MealyMachineIncrementByOne
{
public static void main(String[] args)
{
Scanner sc = new Scanner([Link]);
[Link]("Enter a binary number (Left most bit should be 0):");
String str=[Link]();
char[] str1=[Link]();
char[] str2=new char[[Link]];
int j=[Link]-1;
int q=0;
for(;j>=0;j--)
{
switch(q)
{
case 0 : if(str1[j]=='1')
{
str2[j]='0';
q=0;
}
else
if(q==0 && str1[j]=='0')
18 | Page
{
str2[j]='1';
q=1;
}
break;
case 1: if(str1[j]=='0')
{
str2[j]='0';
q=1;
}
else
if(q==1 && str1[j]=='1')
{
str2[j]='1';
q=1;
}
}
}
for(char c : str2)
[Link](c);
}
}
Instructions: Input : 001
Output :010
Input : 01101
Output : 01110
Roll No. Name of Date of Date of Grade Sign of Sign of
Student Performance Evaluation Student Faculty
19 | Page
