Regular expressions
Regular expressions as a notation for languages: letters, ε, ∅, union, concatenation, star, precedence, denoted language, equivalence of two expressions and Kleene's theorem.
- 21 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Regular expression: what is it?
Show the answer
A formula built from ∅, ε and letters, combined by union (+), concatenation and star, which denotes a language.
The expression is a text, the language is the set of words it denotes: a(a+b)* is an expression, the set of words starting with a is its language.
In the expression ab*+c, what does the star apply to?
- To the letter b only
- To ab
- To the whole of ab+c
- To b and to c
Show the answer
To the letter b only
The star is the highest-precedence operation: it applies only to the smallest piece on its left, here b. The language is {a, ab, abb, …} ∪ {c}.
The union of two expressions is written + in formal language theory, and … in tools such as grep -E or Python.
Show the answer
The union of two expressions is written + in formal language theory, and | in tools such as grep -E or Python.
The trap: in these tools, + is no longer union but a quantifier, "once or more". There a+b describes ab, aab, aaab… and not the language {a, b}, which is written a|b.
Regular language: what is it?
Show the answer
A language denoted by a regular expression or, equivalently, recognized by a finite automaton.
Every finite language is regular. But aⁿbⁿ is not: a finite automaton cannot count up to n when n is unbounded.