CSC 341 (Fall 2021)

Reading: Reading 4: Regular Expressions

Regular Expressions

We’ll study one final model of “regular” computation: the regular expression. Whereas finite automata are machine-like models, the regular expression is a linguistic model. While seemingly unrelated, there are both theoretical and pragmatic connections between the models. As the text illustrates, regular expressions and finite automata are equivalent in computational power. Pragmatically speaking, regular expressions—a fundamental building block for parsing and pattern recognition—are efficiently implemented by translation into equivalent finite automata.

Sipser Reading

Through section 1.3 (Regular Expressions).

Reading Problem (Slightly Unnatural) Give a regular expression for a language \(L\) of strings drawn from the alphabet \(\Sigma = \\{ 0, 1, -, . \\}\) that obey the following properties: