BACHELOR OF COMPUTER SCIENCE

ENGINEERING & TECHNOLOGY

SCHOOL OF COMPUTER SCIENCE AND ENGINEERING

GALGOTIAS UNIVERSITY, GREATER NOIDA

UTTAR PRADESH

Lab File

Compiler Design

Course Code: R1UC627B

Name: Naaz Mohammad Rohan

Admission No: 22SCSE1012667

Semester : VI

1| Page
Output

Make the NFA and DFA of given String : 1 0* 1 (0 + 1)* 1 0

Tool:
JFLAP

Theory:
JFLAP is a software tool designed for experimenting with formal languages and automata theory. It
supports the creation and simulation of various automata, including Deter-ministic Finite Automata
(DFA), Non-deterministic Finite Automata (NFA), Pushdown Automata (PDA), and Turing machines.
Additionally, it facilitates conversions between different representations and enables working with
grammars and regular expressions.

Simulation:
1. Install JFLAP and explore its interface to understand its functionalities.

2. Create a simple DFA that accepts strings over the alphabet {0, 1} ending in “1”:
• States: q0 (start state), q1 (accepting state).
• Transitions: q0 0 q0, q0 1 q1, q1 0 q0, q1 1 q1.
• Start State: q0.
• Accepting State: q1.

3. Test the DFA with the following strings: 01, 11, 00.

Observation:
• JFLAP provides an intuitive interface for creating states and transitions, making it
user- friendly for beginners.

• Test Results:

– 01: Accepted (ends in state q1).

– 11: Accepted (ends in state q1).
– 00: Rejected (ends in state q0).

• The DFA accurately accepts strings ending in “1”, demonstrating JFLAP’s

effec- tiveness in simulating automata.

1
 Experiment 1

Aim/Objective:
Output

if number of 0 and 1 is even then accept the final state other fail

Tool:
JFLAP

Theory:
A Deterministic Finite Automaton (DFA) is a finite state machine where each state has exactly
one transition for each input symbol, and there are no epsilon (ϵ) transitions. A DFA accepts a
string if, after processing the entire input, it ends in an accepting state.

Simulation:
1. Design a DFA in JFLAP that accepts strings over the alphabet {a, b} ending with
the substring “ab”:

• States: q0 (start state), q1, q2 (accepting state).

• Transitions: q0 a q1, q0 b q0, q1 a q1, q1 b q2, q2 a q1, q2 b q0.
• Start State: q0.
• Accepting State: q2.

2. Test the DFA with the following strings: aab, abab, aba, abb.

Observation:
• The DFA was constructed with 3 states, where q2 is the accepting state for
strings ending in “ab”.

• Test Results:

– aab: Accepted (ends in state q2).

– abab: Accepted (ends in state q2).
– aba: Rejected (ends in state q1).
– abb: Rejected (ends in state q0).

• The DFA correctly identifies and accepts only those strings that end with
“ab”, validating its design.
 Experiment 2

Aim/Objective:
Output

Design DFA which accept all string having substring 0011. Using JFLAP generate grammar

Tool:
JFLAP

Theory:
A Non-deterministic Finite Automaton (NFA) allows multiple transitions for the same input
symbol from a given state and can include epsilon (ϵ) transitions. An NFA accepts a string if
there exists at least one path through the automaton that leads to an accepting state after
processing the input.

Simulation:
1. Design an NFA in JFLAP that accepts strings over the alphabet {0, 1} containing
the substring “01”:

• States: q0 (start state), q1, q2 (accepting state).

• Transitions: q0 0 q0, q0 1 q0, q0 0 q1, q1 1 q2, q2 0 q2, q2 1 q2.
• Start State: q0.
• Accepting State: q2.

2. Test the NFA with the following strings: 101, 010, 111, 000.

Observation:
• JFLAP’s interface supports non-determinism by allowing multiple transitions, such
as from q0 on input “0”.

• Test Results:

– 101: Accepted (contains substring “01”).

– 010: Accepted (contains substring “01”).
– 111: Rejected (does not contain “01”).
– 000: Rejected (does not contain “01”).

• The NFA accurately accepts strings containing “01” by exploring possible paths.
 Experiment 3
3
Aim/Objective:
Output

Design NFA { 0 , 1 }, which accept all strings having 3 consecutive 0s and 1s

Tool:
JFLAP

Theory:
The subset construction algorithm converts an NFA to an equivalent DFA by treating each
subset of NFA states as a single DFA state. JFLAP provides an automated tool to perform
this conversion, ensuring the resulting DFA accepts the same language as the original NFA.

Simulation:
1. Use the NFA from Experiment 3, which accepts strings over {0, 1} containing
the substring “01”.

2. Convert the NFA to a DFA using JFLAP’s conversion tool:

3. Test the resulting DFA with the following strings: 101, 010, 111, 000

Observation:
• The original NFA had 3 states, while the converted DFA has 4 states due to subset
• construction.

• Test Results:

– 101: Accepted (contains “01”).

– 010: Accepted (contains “01”).
– 111: Rejected (no “01”).
– 000: Rejected (no “01”).

• The DFA accepts the same language as the NFA, confirming the correctness
of JFLAP’s conversion process.
 Experiment 4

Aim/Objective:
 Experiment 5

Aim/Objective:
Design a automata which accept all string which is divisible by 5 ?

Tool:
JFLAP

Theory:
A regular grammar is a formal grammar equivalent to a DFA, with productions of the form A →
aB or A → a, where A and B are non-terminals and a is a terminal. JFLAP can automatically
derive a regular grammar from a given DFA, reflecting its state transitions.

Simulation:
1. Use the DFA from Experiment 2, which accepts strings over {a, b} ending with “ab”.

2. Convert the DFA to a regular grammar using JFLAP:

3. Generate strings such as ab and aab using the grammar

Observation:
• The grammar’s productions directly correspond to the DFA’s transitions, with q2
(the accepting state) allowing an ϵ production.

• Generated Strings: Strings like ab and aab were generated and confirmed to be
accepted by the DFA.

• The regular grammar accurately generates strings ending in “ab”, consistent with
the DFA’s language.
Output
 Experiment 8

Aim/Objective: