Regular_Expressions_flashcards
What is a regular expression?
A symbolic way of describing a pattern in a set of strings (a language).
Give an example of a regular expression over {0,1} that matches a string with some 0s, a 1, any bit, and a 0.
0*1(0 ∪ 1)0
What is the regular expression for: ‘either empty string or even number of 1s followed by a 0’?
ε ∪ (11)*0
What language does the regex (010)* ∪ (00 ∪ 11)* describe?
Strings made of repeated 010 blocks or repeated 00/11 blocks.
What are the base elements of REG(Σ)?
a ∈ Σ, ε, ∅
What are the 3 operations that extend REG(Σ)?
Union (α ∪ β), Concatenation (αβ), Kleene star (α*)
What is the operator precedence in regular expressions?
Star > Concatenation > Union
What does the regular expression ab* ∪ b*a mean?
The set of strings of the form abⁿ or bⁿa
What does (ab(a ∪ b))* represent?
All strings made by repeating aba or abb patterns.
What is the language of (b ∪ aba)?
Strings over {a,b} with an even number of a’s.
What does L(a) equal for a regular expression?
{a}
What does L(ε) equal?
{ε} — the set containing only the empty word.
What does L(∅) equal?
The empty language — it contains no strings.
What is L(α ∪ β)?
The union of L(α) and L(β): L(α) ∪ L(β)
What is L(αβ)?
The concatenation of L(α) and L(β): L(α)L(β)
What is L(α*)?
The Kleene star of L(α): all strings formed by zero or more concatenations of elements of L(α)
What is the key theorem connecting regular expressions and regular languages?
A language is regular if and only if it can be described by a regular expression.
How do we prove that every regex defines a regular language?
Use induction and closure properties of regular languages.
Can every DFA/NFA be converted into a regex?
Yes — this proves the other direction of the equivalence.
What is the practical method for converting a regex to an NFA?
Build sub-NFAs for components and combine using ε-transitions.
Why should you simplify regular expressions during NFA construction?
To avoid a large and complex NFA from growing out of control.
Name three real-world uses of regular expressions.
Text search, lexical analysis, pattern validation
What are some common tools that use regex?
Text editors, search engines, web scrapers, compilers
How do regular expressions relate to finite automata?
They describe the same class of languages (regular languages).
