EXPERIMENT 1: Introduction of JFLAP (Java Formal Languages and Automata Package) tool for

simulation.

JFLAP, or Java Formal Languages and Automata Package, is a software tool designed for students
and educators in computer science. It specifically targets the field of formal languages and automata
theory, which explores theoretical models of computation.

JFLAP's primary function is to provide an interactive environment for simulating these concepts.
Here's a breakdown of what JFLAP offers:

 Constructing Automata: JFLAP allows you to build various automata models, including
Finite State Automata (FSA), Pushdown Automata (PDA), and Turing Machines (TM). These
models are the building blocks for understanding how languages are recognized and
processed by computers.
 Experimentation: Once you've constructed an automata model, JFLAP lets you test it with
different inputs. This allows you to visualize how the model behaves and verify its
functionality.
 Conversions and Proofs: JFLAP goes beyond just simulation. It can help you explore the
relationships between different automata types. For instance, you can convert a Non-
Deterministic Finite Automata (NFA) to a Deterministic Finite Automata (DFA) and analyze
the process.
 Grammar Exploration: JFLAP supports working with formal grammars, which are another
way to define languages. You can create different grammar types and see how they generate
specific sets of strings.

EXPERIMENT 2: Implementation of Deterministic Finite Automata (DFA) using JFLAP.

JFLAP provides a user-friendly interface to construct and simulate DFAs. Here's a general
guideline for implementing a DFA:

1. Define the Language:

 Start by clearly defining the language your DFA will recognize. This could be a set of
strings containing specific characters or patterns.

2. Build the DFA Model:

 Open JFLAP and choose the "Finite Automaton" option to create a new automaton.
 Use the "State Creator" tool to create states for your DFA. These states represent
different stages the DFA can be in while processing an input string.
 Designate one state as the initial state, where processing begins. You can use the
"Attribute Editor" tool to mark this state.
 Similarly, mark some states as final states using the "Attribute Editor" tool. These
states represent successful recognition of the language.
 Use the "Transition Creator" tool to define transitions between states. Each transition
is labeled with a symbol from the input alphabet.
3. Define Transitions:

 For each state, define transitions for all possible input symbols. Remember, a DFA
has a deterministic transition for every symbol in every state.
 The transition label indicates the symbol that triggers the move and the destination
state after reading that symbol.

4. Consider an Example:

Imagine building a DFA that recognizes strings starting with '0' and ending with '1', with any
number of '0's in between.

 You'll need three states: q0 (initial), q1 (intermediate), and q2 (final).

 q0 will have a transition labeled '0' leading back to itself (representing any number of
leading '0's).
 q0 will also have a transition labeled '1' leading to q2 (reaching the ending '1').
 q1 (after encountering '1') will have no outgoing transitions, signifying an invalid
string after the ending '1'.

5. Simulate and Analyze:

 Once your DFA is built, you can use JFLAP's simulation features to test it with
different input strings.
 The simulation will show the path the DFA takes through the states based on the input
symbols.
 Analyze if the DFA reaches a final state for valid strings and remains elsewhere for
invalid ones.

EXPERIMENT 3: Implementation of Non-deterministic Finite Automata (NFA) using JFLAP.

JFLAP allows you to build Non-deterministic Finite Automata (NFAs) as well, but the
process differs slightly from DFAs due to the inherent non-determinism. Here's how to
implement an NFA using JFLAP:

1. Define the Language:

 Similar to DFAs, start by outlining the language your NFA will recognize.

2. Build the NFA Model:

 The initial steps are the same as building a DFA in JFLAP. Create states, designate an
initial state, and mark final states using the respective tools.
3. Define Transitions:This is where the key difference lies. Unlike DFAs with single
outgoing transitions per symbol, NFAs can have multiple outgoing transitions for a single
symbol from a state.

 These transitions represent the non-deterministic choices the NFA can make during
processing.

4. Consider an Example:

Imagine building an NFA that recognizes strings containing either the substring "ab" or the
symbol "c".

 You can design states q0 (initial), q1, q2 (for "ab"), and q3 (final).
 From q0, create transitions labeled 'a' leading to both q1 and q2 (non-deterministic
choice for "ab").
 q1 will have a transition labeled 'b' leading to q3 (reaching the final state after "ab").
 q2 can have a transition labeled anything (including 'a' or 'b') leading back to itself
(representing unsuccessful "ab" but continuing processing).
 Additionally, from q0, create a separate transition labeled 'c' leading directly to q3
(recognizing the symbol "c").

5. Simulation and Analysis:

 Simulating an NFA in JFLAP might involve showing multiple possible paths the
NFA could take for a given input string due to its non-determinism.
 JFLAP might highlight all reachable states at each step based on the choices made.
 A string is accepted if at least one path leads to a final state.

EXPERIMENT 4: Conversion of Non-deterministic Finite Automata to Deterministic Finite

Automata based on JFLAP.

JFLAP offers a built-in functionality to convert a Non-Deterministic Finite Automata (NFA)

to a Deterministic Finite Automata (DFA). Here's how to leverage it:

1. Build your NFA:

o Create the NFA model in JFLAP using the "State Creator" and "Transition
Creator" tools. Define states, transitions (including those with multiple
outgoing paths for the same symbol), and mark the initial and final states.
2. Navigate to Conversion:
o With your NFA built, go to the "Convert" menu in JFLAP. Select the option
"Convert to DFA."
3. Witness the Magic (Almost):
o JFLAP will automatically create a new window displaying the equivalent DFA
on the right side. The original NFA remains on the left for comparison.
 4. Complete the Conversion (Optional):
o JFLAP might generate an incomplete DFA initially. It might show some states
grouped together. These represent sets of states from the NFA that need
further processing.
5. Expand the Groups (Optional):
o To finalize the conversion, use the buttons provided in JFLAP. Click on the
"Expand Group on (Terminal)" button on the right side. Then, click and hold
on a grouped state and drag it to a blank area to separate them. Repeat for all
grouped states.
6. Analyze the Result:
o Once you have a fully expanded DFA, you can analyze it to ensure it
recognizes the same language as the original NFA. JFLAP's simulation
features can help you compare their behavior.

EXPERIMENT 5: Conversion of Deterministic Finite Automata to Regular Grammar based on

JFLAP.

JFLAP streamlines the conversion process from Deterministic Finite Automata (DFAs) to
Regular Grammars. Here's a breakdown of how to achieve this:

1. Construct your DFA:

o Use JFLAP's tools to create the DFA model. Employ the "State Creator" and
"Transition Creator" to define states, transitions (one per symbol/state for
DFAs), and mark the initial and final states.
2. Initiate Conversion:
o Once your DFA is built, navigate to the "Convert" menu in JFLAP. Select the
option "Convert to Grammar."
3. Witness the Conversion:
o JFLAP will create a new window displaying the corresponding Regular
Grammar on the right side. The original DFA remains on the left for reference.
4. Decoding the Grammar:
o JFLAP assigns variables (usually starting with "q") to each state in the DFA.
The grammar will have productions (rules) based on these variables.
 Transitions in the DFA translate to productions in the grammar. For
example, a transition from state q0 to q1 on symbol 'a' becomes a
production rule "q0 → a q1" in the grammar.
 Final states in the DFA might have additional productions of the form
"qF → λ" (lambda), signifying they can accept an empty string (ε).
5. Analyze the Grammar:
o Verify if the generated grammar accurately reflects the language recognized
by the DFA. You can manually test strings using the grammar's productions.
EXPERIMENT 6: Conversion of Deterministic Finite Automata to Regular Expression based on
JFLAP.

JFLAP actually doesn't directly convert Deterministic Finite Automata (DFAs) to Regular
Expressions. However, it provides functionalities that can help you achieve this conversion
indirectly. Here's how:

1. Build your DFA:

o As usual, create the DFA model in JFLAP using the "State Creator" and
"Transition Creator" tools. Define states, transitions (one per symbol/state for
DFAs), and mark the initial and final states.
2. Convert to Generalized Transition Graph (GTG):
o JFLAP's conversion process goes through an intermediate step. Navigate to
the "Convert" menu and select "Convert to RE" (Regular Expression).
3. Merge States (Optional):
o JFLAP might display a prompt asking if you want to merge equivalent states.
This creates a more concise Generalized Transition Graph (GTG), which is a
single-final-state automaton with all states reachable from the initial state.
Choose "Yes" if you want to simplify the visualization.
4. Analyze the GTG:
o The GTG shows each state and its transitions labeled with symbols. Now
comes the manual part: Analyze the paths from the initial state to final states.
5. Construct the Regular Expression (Manually):
o Based on the analyzed paths in the GTG, construct the regular expression by
concatenating the symbols along each path leading to a final state. Use
symbols like "|" (OR) for alternative paths if needed.

EXPERIMENT 7: Conversion of Regular Expression to Deterministic Finite Automata based on

JFLAP.

JFLAP excels at converting Regular Expressions (REs) to Deterministic Finite Automata

(DFAs). Here's a step-by-step guide:

1. Enter your Regular Expression:

o Open JFLAP and choose the "Regular Expression" option. A text box will
appear where you can input your desired RE.
2. Convert to Non-deterministic Finite Automata (NFA) (Optional):
o JFLAP offers an intermediate conversion step. Although not strictly necessary
for DFA creation, you can convert the RE to an NFA first using the "Convert"
-> "Convert to NFA" option. This can be helpful for visualizing the initial
stages of the process.
3. Convert to Deterministic Finite Automata:
o Whether you converted to an NFA or not, navigate to the "Convert" menu
again. This time, select "Convert to DFA."
 4. Witness the Conversion:
o JFLAP will create a new window displaying the equivalent DFA on the right
side. The original RE (or the NFA if you used the intermediate step) remains
on the left for reference.
5. Analyze the DFA:
o Verify if the resulting DFA accurately recognizes the language specified by
your regular expression. You can use JFLAP's simulation features to test the
DFA with different input strings.

EXPERIMENT 8: Design a Context Free Grammars (CFG) with Single Symbols based on JFLAP.

JFLAP can certainly help in designing and experiment with various CFGs that use both non-
terminal and terminal symbols. Here's a basic example:

Language: Set of strings with zero or more 'a's followed by a single 'b'

Grammar in JFLAP:

1. Open JFLAP and select the "Grammar" option.

2. Define two symbols:
o Non-terminal: S (represents the starting point)
o Terminal: a
3. Create productions (rules):
o S -> aS (Allows for zero or more 'a's)
o S -> b (Terminates with a single 'b')

This CFG can generate strings like "b", "ab", "aab", "aaab", etc.

JFLAP allows you to explore various features like:

 Adding more non-terminals and terminals for complex languages.

 Modifying productions to create different sets of strings.
 Parsing input strings to see if they can be generated by the grammar.

By experimenting with JFLAP and understanding the role of non-terminals, you can
effectively design and analyze Context-Free Grammars for various language representations.

EXPERIMENT 9: Design a Context Free Grammars (CFG) with Multiple Symbols based on JFLAP.

JFLAP is a great tool for creating and experimenting with Context-Free Grammars (CFGs)
that utilize multiple symbols (both terminals and non-terminals). Here's an example:
Language: Set of strings starting with 'a' and ending with 'b', with any number of '0's and '1's
in between.

Steps in JFLAP:

1. Open JFLAP and choose "Grammar."

2. Define Symbols:
o Terminals:
 a
 b
 0
 1
oNon-terminal:
 S (represents the starting point)
3. Create Productions:
o These rules define how to rewrite non-terminals into strings.
 S -> a X b (Start with 'a', followed by X, and end with 'b')
 X -> X 0 (X can be rewritten as itself followed by '0')
 X -> X 1 (X can also be rewritten as itself followed by '1')
 X -> ε (Epsilon, signifying X can be empty)

Explanation of Productions:

 The first rule (S -> a X b) defines the overall structure: starting with 'a', followed by
something represented by X, and ending with 'b'.
 The next two rules (X -> X 0 and X -> X 1) allow for any number of '0's or '1's by
letting X rewrite itself with either symbol.
 The final rule (X -> ε) enables X to be empty, allowing the string to have zero
characters between 'a' and 'b'.

EXPERIMENT 10: Implement the LL Parsing using JFLAP

JFLAP supports functionalities related to LL(1) Parsing, a specific parsing technique for
Context-Free Grammars (CFGs). Here's a breakdown of how to implement LL(1) Parsing
using JFLAP:

1. Create your CFG:

 Open JFLAP and choose the "Grammar" option. Define your non-terminal and
terminal symbols, and create productions (rules) for your desired language.

2. Build the LL(1) Parse Table:

 Once your CFG is defined, navigate to the "Input" menu in JFLAP. Select "Build
LL(1) Parse Table."

3. Compute FIRST and FOLLOW Sets (Optional):

  JFLAP might prompt you to calculate the FIRST and FOLLOW sets for each symbol
(terminal and non-terminal) in your grammar.
o FIRST(X) is the set of terminal symbols that can appear as the first symbol in
a string derived from X.
o FOLLOW(X) is the set of terminal symbols that can directly follow X in a
valid derivation.
 While JFLAP can sometimes automate this step, understanding these sets is crucial
for LL(1) parsing. You might need to calculate them manually for complex grammars.

4. Interpret the Parse Table:

 JFLAP will generate a table showing entries for each combination of a non-terminal
symbol (on the left) and a terminal symbol (on the top). These entries represent
parsing actions, which can be:
o A production rule (e.g., A -> aBb) indicating how to rewrite the non-terminal.
o An error message signifying an invalid combination.

5. Parse an Input String (Optional):

 JFLAP offers a parsing feature. You can enter an input string and use the parse table
to determine if the string can be generated by your grammar. JFLAP will guide you
through the parsing steps based on the table entries.

EXPERIMENT 11: Implement the LR Parsing using JFLAP

JFLAP doesn't directly support implementing LR Parsing (specifically SLR, LALR, or

LR(0)) in the same way it does for LL(1) parsing. However, JFLAP offers functionalities that
can be helpful for understanding and working with LR parsers. Here's what you can do:

Understanding LR Parsing:

 LR Parsing techniques (SLR, LALR, LR(0)) are bottom-up parsing approaches for
CFGs. They work by building the parse tree from the rightmost side of the input
string.
 JFLAP doesn't directly build LR parsing tables. However, you can leverage its
features to gain insights into LR parsing:
o Build the CFG: Create your grammar in JFLAP, defining non-terminals,
terminals, and productions. Understanding the grammar is essential for any
parsing technique.
o Simulate DFA/NFA (Optional): If your grammar is ambiguous or requires
lookahead symbols, it might be related to an SLR or LALR parser. JFLAP
allows you to build Deterministic Finite Automata (DFAs) or Non-
deterministic Finite Automata (NFAs) .
EXPERIMENT 12: Design a Regular Expression through JFLAP.

JFLAP excels at designing Regular Expressions (REs). Here's how you can achieve this:

1. Open JFLAP: Launch JFLAP and choose the "Regular Expression" option.
2. Construct your RE:
o In the text box provided, enter your desired regular expression using the
following symbols:
 Letters (a-z, A-Z) for literal characters.
 Numbers (0-9) for literal digits.
 Special characters like:
 . (dot) for any single character.
 * (asterisk) for zero or more repetitions of the preceding
element.
 + (plus) for one or more repetitions of the preceding element.
 ? (question mark) for zero or one repetition of the preceding
element.
 | (pipe) for OR (alternative choices).
 [] (brackets) for a character class (set of characters).
3. Validate (Optional):
o JFLAP might offer a basic validation check to ensure your RE is syntactically
correct.

EXPERIMENT 13: Develop a Lexical Analyzer to recognize a few patterns. (Using C)

#include <stdio.h>

#include <ctype.h>

#include <string.h>

#define MAX_IDENTIFIER_LENGTH 256

int isLetterOrUnderscore(char ch) {

return (isalpha(ch) || ch == '_');

}
int isKeyword(char* str) {

static char* keywords[] = {"int", "float", "char"}; // Adjust keywords as needed

for (int i = 0; i < sizeof(keywords) / sizeof(keywords[0]); i++) {

if (strcmp(str, keywords[i]) == 0) {

return 1;

return 0;

int main() {

char buffer[MAX_IDENTIFIER_LENGTH + 1];

int i = 0;

char ch;

printf("Enter a string: ");

fgets(buffer, sizeof(buffer), stdin); // Read from standard input

while (buffer[i] != '\0' && buffer[i] != '\n') {

if (isLetterOrUnderscore(buffer[i])) {

while (isLetterOrUnderscore(buffer[i]) || isdigit(buffer[i])) {

i++;

buffer[i] = '\0'; // Terminate the substring

if (isKeyword(buffer)) {

printf("Keyword: %s\n", buffer);

return 0;

}
EXPERIMENT 14: Implementation of Lexical Analyzer for IF statements. (Using C)

#include <stdio.h>

#include <ctype.h>

#include <string.h>

#define MAX_IDENTIFIER_LENGTH 256

int isLetterOrUnderscore(char ch) {

return (isalpha(ch) || ch == '_');

int main() {

char buffer[MAX_IDENTIFIER_LENGTH + 1];

int i = 0;

char ch;

printf("Enter a string: ");

fgets(buffer, sizeof(buffer), stdin);

while (buffer[i] != '\0' && buffer[i] != '\n') {

if (isLetterOrUnderscore(buffer[i])) {

while (isLetterOrUnderscore(buffer[i]) || isdigit(buffer[i])) {

i++;

buffer[i] = '\0';

if (strcmp(buffer, "if") == 0) {
 printf("IF Keyword Found\n");

break;

i = 0;

} else {

i++;

return 0;

EXPERIMENT 15: Implement Operator Precedence parser. (Using C

#include <stdio.h>

#include <ctype.h>

#include <string.h>

#define MAX_SIZE 50

int isOperand(char ch) {

return isdigit(ch);

int getPrecedence(char op) {

switch (op) {

case '+':

case '-':
 return 1;

case '*':

case '/':

return 2;

default:

return -1; // Invalid operator

void infixToPostfix(char* infix, char* postfix) {

int stack[MAX_SIZE];

int top = -1;

char ch, x;

for (int i = 0; infix[i] != '\0'; i++) {

ch = infix[i];

if (isOperand(ch)) {

// Append operand to postfix

strcat(postfix, &ch);

} else if (ch == '(') {

// Push '(' to stack

stack[++top] = ch;

} else if (ch == ')') {

// Pop and append from stack until '(' is encountered

while (top != -1 && stack[top] != '(') {

strcat(postfix, &stack[top--]);

if (top == -1) {

printf("Error: Missing opening parenthesis\n");

 exit(1); // Exit program on missing opening parenthesis

// Pop '('

x = stack[top--];

} else {

// Get precedence of current operator

int prec = getPrecedence(ch);

// Pop elements from stack with higher or equal precedence

while (top != -1 && stack[top] != '(' && getPrecedence(stack[top]) >= prec) {

strcat(postfix, &stack[top--]);

// Push current operator to stack

stack[++top] = ch;

// Pop remaining operators from stack

while (top != -1) {

strcat(postfix, &stack[top--]);

int main() {

char infix[MAX_SIZE], postfix[MAX_SIZE * 2]; // Double the size for postfix

printf("Enter an infix expression: ");

fgets(infix, sizeof(infix), stdin);

postfix[0] = '\0'; // Initialize postfix as empty string

 infixToPostfix(infix, postfix);

printf("Postfix expression: %s\n", postfix);

return 0;