Regular Expressions and NFA
Ganesh Lalitha Gopalakrishnan · 2019
This chapter presents regular expressions (REs) to provide the expression syntax for typing in nondeterministic finite automata (NFA) into a computer, through the interactive use of 2nfafunction and to solve a non-trivial language design problem. Getting REs wrong can open up security holes; one must employ good checkers. It also presents a mini-compiler that parses REs and emits NFA. A cool application of REs is to calculate what postage values one can attain using given stamp values a related problem is the McNugget number. REs pack a considerable punch in small syntactic confines. This makes them quite suitable for use in various settings—in parsing user web-forms, rejecting malformed command-line inputs, detecting malware within internet packets, etc. REs are either primitive ones or simple REs that are glued together through union, concatenation, and star. These results in the NFA which is much more tedious to obtain than the RE designed. However, human effort-wise, arriving at this NFA design is not that difficult.