FP Homework 3 extension
Jump to navigation
Jump to search
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.