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.