Bihar STET Computer Science – Compiler Design Set 3

firstpos(n) returns the set of positions at the leaves of the subexpression rooted at n that can match the first symbol of a string generated by that subexpression.

followpos(i) defines the set of positions in the syntax tree that can immediately follow position i in a valid string matching the augmented regular expression.

nullable(n) is True if the subexpression rooted at node n can generate the empty string $\epsilon; otherwise False$.

The Myhill-Nerode theorem states that a language L is regular iff the number of equivalence classes under its right-invariant equivalence relation (Myhill-Nerode relation) is finite.

The State Elimination method iteratively removes non-initial and non-final states from a Generalized NFA to derive an equivalent regular expression.