Assignment #3A and # 3B Solution

$30.00

Description

# 3A In this programming assignment you will implement -NFA to DFA conversion mechanishm. The specific input-output requirements to your program are given below:

Input: An -NFA N with alphabet Σ = {0, 1}. The description of the NFA must be provided to the program through a file. An example format for a specific -NFA is given below. The first row includes all the states; the second row include the starting state; the third row includes all the final states; fourth row describes three transitions from q0 on input symbols 0, 1 and respectively; fifth row does the same with respect to q1; and so on.

q0 q1 q2 q3

q0

q1

{q1 } φ {q1, q2 }

{q1, q2} {q1} {q3}

{q1 } φ φ

{q2 } φ {q2}

Output: An equivalent DFA D, i.e. L(D) = L(N ). The output, i.e., the description

(similar to input NFA description) of equivalent DFA D must be copied into a file.

Your program must also provide a graphical drawing of the equivalent DFA (you may use standard libraries for this task).

# 3B In this programming assignment you will implement membership checking of an arbitrary binary string with respect to the language of a given -NFA. The specific input- output requirements to your program are given below:

Input: An -NFA N with alphabet Σ = {0, 1} and a string w {0, 1} . The input N

will be provided in the format given in Assignment # 3A.

Output: Yes, if w L(N ); No otherwise.

Important Instructions!!

Combine both 3A and 3B in one program.

20 marks for correctness of # 3A.

10 marks for correctness of # 3B.

The rest 10 will account for programming efficiency and proficiency.

In this programming assignment you will implement membership checking of an arbitrary string with respect to the language of a given regular expression. The specific input-output requirements to your program are given below:

Input: A Regular expression R over a alphabet Σ, and a string w Σ . The Σ need not be {0, 1}. Thus, as input, you must also provide the alphabet Σ.

Output: Yes, if w L(R); No otherwise.

Your program should ideally be doing the following:

Function making sense of regular expressions.

Function that converts regular expressions to its equivalent -NFA N .

Using your # 3B program (modify it to support any alphabet Σ) to check if w L(N ).

Note: 25 marks for correctness of # 3C. The rest 5 will account for programming efficiency and proficiency.