Project $1-$ Convert a NFA to a DFA

Project Description

Theorem $2\mathrm{.}2$ in the textbook shows that for any

nondeterministic finite accepter, there exists a

deterministic finite accepter such that both accept the

same language. The proof of the theorem also describes

the procedure nfa$-$to$-$dfa to demonstrate the conversion

$($ref$.$ Page $61-62)$ from a NFA to a DFA. In this project, you

will implement this procedure using a programming

language.

Project Requirements

Design the data structure of representing both

deterministic and nondeterministic finite

accepters. The input nfa can be stored as a matrix,

where the columns correspond to input symbols,

while the rows correspond to states. The matrix

cells are subsets of states representing the

transitions for the corresponding states and

symbols. The output of your program should also be

a matrix representing the dfa, whose each cell

should be a single state.

Choose your programming language, and

implement the procedure nfa$-$to$-$dfa.

Test your implementation using the following

inputs: $$

Submit Assignment Assignment Details

implement the procedure nfa$-$to$-$dfa.

Test your implementation using the following

inputs:

Input nfa defined by

$(q_0,a)=\{q_0,q_1\},(q_1,(b))=\{q_1,q_2\},(q_2,a)=\{q_2\}$

with initial state $q_0$ and final state $q_1.$

Input nfa defined by

$(q_0,a)=\{q_0,q_1\},(q_1,(b))=\{q_1,q_2\},(q_2,a)=\{q_2\},(q_0,)$

$=\{q_2\},$

with initial state $q_0$ and final state $q_1.$

Input nfd defined by

$(q_0,a)=\{q_0,q_1\},(q_1,b)=\{q_1,q_2\},(q_2,a)=\{q_2\},d(q_1,)$

$=\{q_1,q_2\},$

with initial state $q_0$ and final state $q_1.$

Input nfd defined by

$(q_0,a)=\{q_0,q_1\},(q_0,(b))=\{q_1\},(q_1,a)=\{q_2\},(q_1,(b))=$

$\{q_2\},$

$(q_2,(b))=\{q_2\},$Convert a NFA to a DFA Assignment Details

with initial state $q_0$ and final state $q_1.$

Input nfd defined by

$(q_0,a)=\{q_0,q_1\},(q_1,b)=\{q_1,q_2\},(q_2,a)=\{q_2\},d(q_1,)$

$=\{q_1,q_2\},$

with initial state $q_0$ and final state $q_1.$

Input nfd defined by

$(q_0,a)=\{q_0,q_1\},(q_0,(b))=\{q_1\},(q_1,a)=\{q_2\},(q_1,(b))=$

$\{q_2\},$

$(q_2,(b))=\{q_2\},$

with initial state $q_0$ and final state $q_1.$

Project Submission

The data structure design.

The program design such as class diagram $($if you're

using OO language$)$ or program structure $($if you're

using procedural language$),$ and source co

for any nondeterministic finite accepter, there exists a deterministic finite accepter such that both accept the same language. The proof of the theorem also describes the procedure nfa$-$to$-$dfa to demonstrate the conversion $($ref$.$ Page $61-62)$ from a NFA to a DFA. In this project, you will implement this procedure using a programming language.

$)=\{$q$2\},\backslash$delta $($q$0,\backslash$lambda $)=\{$q$2\},$

with initial state q$0$ and final state q$1.$

Input nfd defined by

$\backslash$delta $($q$0,$ a$)=\{$q$0,$ q$1\},\backslash$delta $($q$1,$ b$)=\{$q$1,$ q$2\},\backslash$delta $($q$2,$ a$)=\{$q$2\},$ d$($q$1,\backslash$lambda $)=\{$q$1,$ q$2\},$

with initial state q$0$ and final state q$1.$

Input nfd defined by

$\backslash$delta $($q$0,$ a$)=\{$q$0,$ q$1\},\backslash$delta $($q$0,$ b$)=\{$q$1\},\backslash$delta $($q$1,$ a$)=\{$q$2\},\backslash$delta $($q$1,$ b$)=\{$q$2\},$

$\backslash$delta $($q$2,$ b$)=\{$q$2\},$

with initial state q$0$ and final state q$1.$

Project Submission

The data structure design.

The program design such as class diagram $($if you$$re using OO language$)$ or program structure $($if you$$re using procedural language$),$ and source code.

The test results for the given inputs. You may add more tests.