Experiment 1

Aim/Objective:
To understand the basics of JFLAP (Java Formal Languages and Automata Package) tool for
simulation.

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
Output
 Experiment 2

Aim/Objective:
To implement a Deterministic Finite Automaton (DFA) using JFLAP.

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.
Output

2
 Experiment 3

Aim/Objective:
To implement a Non-deterministic Finite Automaton (NFA) using JFLAP.

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.
Output

3
 Experiment 4

Aim/Objective:
To convert a Non-deterministic Finite Automaton (NFA) to a Deterministic Finite Au-
tomaton (DFA) using JFLAP.

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.
Output

4
 Experiment 5

Aim/Objective:
To convert a Deterministic Finite Automaton (DFA) to a Regular Grammar using JFLAP.

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

5
 Experiment 6

Aim/Objective:
To convert a Deterministic Finite Automaton (DFA) to a Regular Expression using JFLAP.

Tool:
JFLAP

Theory:
A regular expression describes the same language as a DFA. JFLAP employs the state
elimination method to convert a DFA into an equivalent regular expression, which can then
be used to represent the language in a more compact form.

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

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

• Resulting Regular Expression: (a + b)∗ ab.

3. Test the regular expression by converting it back to a DFA in JFLAP and testing with
strings aab and abab.

Observation:
• The resulting regular expression (a + b)∗ ab accurately describes the language of
strings ending in “ab”.

• Test Results: The converted DFA accepts aab and abab, consistent with the original
DFA’s behavior.

• JFLAP’s conversion process is efficient and produces a correct regular expression.

6
 Experiment 7

Aim/Objective:
To convert a Regular Expression to a Deterministic Finite Automaton (DFA) using JFLAP.

Tool:
JFLAP

Theory:
A regular expression can be converted to an NFA using Thompson’s construction al-gorithm,
and subsequently to a DFA using the subset construction method. JFLAP automates this
process, allowing users to visualize and test the resulting DFA.

Simulation:
1. Use the regular expression (a + b)∗ b, which represents strings over {a, b} ending in
“b”.

2. Convert the regular expression to an NFA, then to a DFA using JFLAP:

• NFA Structure: Includes states for the (a + b)∗ loop and a transition on b to an
accepting state.
• Resulting DFA States: q0 (start state), q1 (accepting state).
• Transitions: q0 a q0, q0 b q1, q1 a q0, q1 b q1.

3. Test the DFA with the following strings: ab, bb, aa, b.

Observation:
• The NFA initially had multiple states, but the DFA simplified to 2 states after
conversion.

• Test Results:

– ab: Accepted (ends in state q1).

– bb: Accepted (ends in state q1).
– aa: Rejected (ends in state q0).
– b: Accepted (ends in state q1).

• The DFA correctly accepts strings ending in “b”, matching the language defined by the
regular expression.
Output

7
 Experiment 8

Aim/Objective:
To design a Context-Free Grammar (CFG) with single symbols using JFLAP.

Tool:
JFLAP

Theory:
A Context-Free Grammar (CFG) consists of variables, terminals, production rules, and a start
symbol, generating languages that can be recognized by a Pushdown Automaton (PDA). In
this context, “single symbols” refers to terminals being individual characters (e.g., a, b).

Simulation:
1. Design a CFG in JFLAP for the language {anbn | n ≥ 0}:
• Productions: S → a S b | ϵ.
2. Generate strings such as ϵ, ab, and aabb using the CFG.

Observation:
• The CFG’s productions (S → a S b | ϵ) successfully generate strings like ϵ, ab, and aabb.

• PDA Test Results:

– aabb: Accepted (balanced a’s and b’s).

– aab: Rejected (unbalanced a’s and b’s).

• The PDA correctly validates the CFG’s language, accepting only strings with equal
numbers of a’s and b’s in the correct order.

Output