Description

5/5 - (2 votes)

# 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.