Scribd
Upload
3 views3 pages

CD Program 3

The document provides a C++ implementation for constructing a Non-deterministic Finite Automaton (NFA) from a regular expression in postfix notation. It includes functions for creating NFAs for symbols, concatenation, union, and Kleene star operations, along with a main function to process the input regex and output the resulting NFA states. The example input 'ab.*' demonstrates the construction of the NFA and prints the start and end states.

Uploaded by

RK
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views3 pages

CD Program 3

The document provides a C++ implementation for constructing a Non-deterministic Finite Automaton (NFA) from a regular expression in postfix notation. It includes functions for creating NFAs for symbols, concatenation, union, and Kleene star operations, along with a main function to process the input regex and output the resulting NFA states. The example input 'ab.*' demonstrates the construction of the NFA and prints the start and end states.

Uploaded by

RK
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

3. Construction of nfa from regular expression in c++.

#include <iostream>
#include <stack>
using namespace std;

int stateCount = 0;

struct NFA
{
int start;
int end;
};

// Create NFA for symbol


NFA symbolNFA(char c)
{
NFA n;
[Link] = stateCount++;
[Link] = stateCount++;

cout << [Link] << " --" << c << "--> " << [Link] << endl;
return n;
}

// Concatenation
NFA concatenate(NFA n1, NFA n2)
{
cout << [Link] << " --ε--> " << [Link] << endl;
return {[Link], [Link]};
}

// Union
NFA unionNFA(NFA n1, NFA n2)
{
NFA n;
[Link] = stateCount++;
[Link] = stateCount++;

cout << [Link] << " --ε--> " << [Link] << endl;
cout << [Link] << " --ε--> " << [Link] << endl;
cout << [Link] << " --ε--> " << [Link] << endl;
cout << [Link] << " --ε--> " << [Link] << endl;

return n;
}

// Kleene star
NFA kleeneStar(NFA n1)
{
NFA n;
[Link] = stateCount++;
[Link] = stateCount++;

cout << [Link] << " --ε--> " << [Link] << endl;
cout << [Link] << " --ε--> " << [Link] << endl;
cout << [Link] << " --ε--> " << [Link] << endl;
cout << [Link] << " --ε--> " << [Link] << endl;

return n;
}

int main()
{
string regex;
cout << "Enter postfix regular expression: ";
cin >> regex;

stack<NFA> st;

for (char c : regex)


{
if (isalnum(c))
{
[Link](symbolNFA(c));
}
else if (c == '.')
{
NFA n2 = [Link](); [Link]();
NFA n1 = [Link](); [Link]();
[Link](concatenate(n1, n2));
}
else if (c == '|')
{
NFA n2 = [Link](); [Link]();
NFA n1 = [Link](); [Link]();
[Link](unionNFA(n1, n2));
}
else if (c == '*')
{
NFA n1 = [Link](); [Link]();
[Link](kleeneStar(n1));
}
}

NFA result = [Link]();


cout << "\nStart State: " << [Link] << endl;
cout << "End State: " << [Link] << endl;

return 0;
}

Input:

ab. *

Output:

0 --a--> 1
2 --b--> 3
1 --ε--> 2
4 --ε--> 0
4 --ε--> 5
3 --ε--> 0
3 --ε--> 5
Start State: 4
End State: 5

You might also like