FP Homework 3 extension

Conversion of regular expressions to deterministic finite automaton

• Define a data structure describing regular expressions.
• Create a function converting given regular expression to non-deterministic finite automaton.
• Create a function converting this non-deterministic automaton to its deterministic counterpart.

Compute first and follow sets

• Define a representation for context-free grammars.
• Create a function computing non-terminals, which can be rewritten to 'epsilon' (empty set).
• Create a function computing the first set for giver sequence of symbols (terminals and non-terminals).
• Create a function computing the follow set for the given non-terminal.

Using regular expressions to search in a text

• Define a data structure describing regular expressions.
• Create a function converting given regular expression to non-deterministic finite automaton.
• Run this non-deterministic automaton on a given text to find sub-strings generated by the original regular expression.