Using Python PLY implement the RE to DFA conversion algorithm. Once the DFA is constructed, prompt the user for input strings and report "MATCH" if the string is accepted by the DFA and "NO MATCH" otherwise. Please refer to the notes on the algorithm at RegExp2DFA.pdf". NOTES:Since the expression tree nodes have various attributes associated with them, such as nullable, firstpos, lastpos, etc., this project can benefit from building a traditional tree data structure with nodes and pointers to children nodes. I am providing a skeletal file, RENode.py, which you should use to construct the tree data structure in REParser.py and also use in the main program to compute the various functions such as nullable, firstpos, and lastpos.We shall use the ^ character to denote the ε regular expression.Submit the following files: RE.py, RELexer.py, REParser.py, RENode.py, and an optional README under assignment p1 Here is a sample run:Mac-mini:re raj$ python3 RE.pyREGEX: (a+b)*aa(a+b)*;INPUT STRING: aa;МАТCHINPUT STRING: ababab;NO MATCHINPUT STRING: abaabbbb;MATCHINPUT STRING: bbbaabbbbbbb;МАТCHINPUT STRING: exit;REGEX: a(a+b)*b + b(a+b)*a;INPUT STRING: abba;NO MATCHINPUT STRING: abbb;МАТCHINPUT STRING: baba;MATCHINPUT STRING: babb;NO MATCHINPUT STRING: aaaaaaaaabbbbbbbb;МАТCHINPUT STRING: bbbbbbbaaaaaa;МАТCHINPUT STRING: ab;MATCHINPUT STRING: ba;MATCHINPUT STRING: aa;NO MATCHINPUT STRING: bb;NO MATCHINPUT STRING: exit;REGEX: exit; Mac-mini:re raj$ python3 RE.py -dfaREGEX: (a+b)*aa (a+b)*;start_state({1, 2, 3}).delta({1, 2, 3}, a,{1, 2, 3, 4}).delta({1, 2, 3},b,{1, 2, 3}).delta({1, 2, 3, 4}, a,{1, 2, 3, 4, 5, 6, 7}).delta({1, 2, 3, 4},b,{1, 2, 3}).delta({1, 2, 3, 4, 5, 6, 7}, a,{1, 2, 3, 4, 5, 6, 7}).delta ({1, 2, 3, 4, 5, 6, 7},b,{1, 2, 3, 5, 6, 7}).delta ({1, 2, 3, 5, 6, 7}, a,{1, 2, 3, 4, 5, 6, 7}).delta({1, 2, 3, 5, 6, 7},b,{1, 2, 3, 5, 6, 7}).delta(set(),a, set()).delta(set(), b,set()).final_state({1, 2, 3, 4, 5, 6, 7}).final_state({1, 2, 3, 5, 6, 7}).INPUT STRING: abab;NO MATCHINPUT STRING: abaabb;МАТCHINPUT STRING: exit;REGEX: (1+2+3+4+5+6+7+8+9) (0+1+2+3+4+5+6+7+8+9)*;INPUT STRING: 976;MATCHINPUT STRING: 0976;NO MATCHINPUT STRING: 123450;МАТCHINPUT STRING: ab12;Invalid input stringINPUT STRING: exit;REGEX: exit;Mac-mini:re rajs vi RE.pyMac-mini:re raj$ python3 RE.pyREGEX: (1+2+3+4+5+6+7+8+9) (0+1+2+3+4+5+6+7+8+9)*;INPUT STRING: 976;МАТCHINPUT STRING: 0976;NO MATCHINPUT STRING: 123450;MATCHINPUT STRING: ab12;NO MATCH: Invalid input characterINPUT STRING: exit;REGEX: exit;

Here is the solution for the above one:

Answered: Using Python PLY implement the RE to…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Using Python PLY implement the RE to DFA conversion algorithm. Once the DFA is constructed, prompt the user for input strings and report "MATCH" if the string is accepted by the DFA and "NO MATCH" otherwise. Please refer to the notes on the algorithm at RegExp2DFA.pdf".

NOTES:

Since the expression tree nodes have various attributes associated with them, such as nullable, firstpos, lastpos, etc., this project can benefit from building a traditional tree data structure with nodes and pointers to children nodes. I am providing a skeletal file, RENode.py, which you should use to construct the tree data structure in REParser.py and also use in the main program to compute the various functions such as nullable, firstpos, and lastpos.
We shall use the ^ character to denote the ε regular expression.

Submit the following files: RE.py, RELexer.py, REParser.py, RENode.py, and an optional README under assignment p1

Here is a sample run:
Mac-mini:re raj$ python3 RE.py
REGEX: (a+b)*aa(a+b)*;
INPUT STRING: aa;
МАТCH
INPUT STRING: ababab;
NO MATCH
INPUT STRING: abaabbbb;
MATCH
INPUT STRING: bbbaabbbbbbb;
МАТCH
INPUT STRING: exit;
REGEX: a(a+b)*b + b(a+b)*a;
INPUT STRING: abba;
NO MATCH
INPUT STRING: abbb;
МАТCH
INPUT STRING: baba;
MATCH
INPUT STRING: babb;
NO MATCH
INPUT STRING: aaaaaaaaabbbbbbbb;
МАТCH
INPUT STRING: bbbbbbbaaaaaa;
МАТCH
INPUT STRING: ab;
MATCH
INPUT STRING: ba;
MATCH
INPUT STRING: aa;
NO MATCH
INPUT STRING: bb;
NO MATCH
INPUT STRING: exit;
REGEX: exit;

Mac-mini:re raj$ python3 RE.py -dfa
REGEX: (a+b)*aa (a+b)*;
start_state({1, 2, 3}).
delta({1, 2, 3}, a,{1, 2, 3, 4}).
delta({1, 2, 3},b,{1, 2, 3}).
delta({1, 2, 3, 4}, a,{1, 2, 3, 4, 5, 6, 7}).
delta({1, 2, 3, 4},b,{1, 2, 3}).
delta({1, 2, 3, 4, 5, 6, 7}, a,{1, 2, 3, 4, 5, 6, 7}).
delta ({1, 2, 3, 4, 5, 6, 7},b,{1, 2, 3, 5, 6, 7}).
delta ({1, 2, 3, 5, 6, 7}, a,{1, 2, 3, 4, 5, 6, 7}).
delta({1, 2, 3, 5, 6, 7},b,{1, 2, 3, 5, 6, 7}).
delta(set(),a, set()).
delta(set(), b,set()).
final_state({1, 2, 3, 4, 5, 6, 7}).
final_state({1, 2, 3, 5, 6, 7}).
INPUT STRING: abab;
NO MATCH
INPUT STRING: abaabb;
МАТCH
INPUT STRING: exit;
REGEX: (1+2+3+4+5+6+7+8+9) (0+1+2+3+4+5+6+7+8+9)*;
INPUT STRING: 976;
MATCH
INPUT STRING: 0976;
NO MATCH
INPUT STRING: 123450;
МАТCH
INPUT STRING: ab12;
Invalid input string
INPUT STRING: exit;
REGEX: exit;
Mac-mini:re rajs vi RE.py
Mac-mini:re raj$ python3 RE.py
REGEX: (1+2+3+4+5+6+7+8+9) (0+1+2+3+4+5+6+7+8+9)*;
INPUT STRING: 976;
МАТCH
INPUT STRING: 0976;
NO MATCH
INPUT STRING: 123450;
MATCH
INPUT STRING: ab12;
NO MATCH: Invalid input character
INPUT STRING: exit;
REGEX: exit;

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions