4.4.2.3–4.4.2.4 - Regular expressions and regular languages (C#)
Describe sets of strings using regular expressions, relate them to finite-state machines and apply simple patterns in C#. This route uses written C# tasks and is incomplete: runnable support pending.
Strings and regular languages
A language is a set of strings, and a regular expression describes which strings belong to that set.
An alphabet is the set of available symbols. Over , strings include , , and the empty string . The empty string has length zero; it is different from a string containing a blank-space character. A language need not be a natural language or a programming language: “all strings of a's and b's beginning with a” is a language.
Regular language
A language is regular if a regular expression can represent it. Equivalently, it is a language accepted by a finite-state machine.
The expression denotes one initial a followed by zero or more a's or b's. Its language contains . It excludes , because the initial a is compulsory, and excludes , because its first symbol is b. Matching the whole string asks whether it is a member of the language; finding a matching substring asks a different question. The string ba contains the substring a but is not itself in this language.
A regular expression describes a set rather than a particular order of enumeration. There are infinitely many strings in this example, but each individual string is finite and can be checked by a finite-state machine. An infinite set does not require an infinite number of states.
Repetition, choice and grouping
Regular-expression operators specify repetition and alternatives, and grouping determines which expression an operator affects.
| Notation | Meaning | Example language members |
|---|---|---|
| Zero or more a's | ||
| One or more a's | ||
| Zero or one a | ||
| a or b | ||
| Zero or more repetitions of the pair ab |
Writing adjacent expressions means concatenation. In , only b is repeated: . In , the entire pair is repeated. Neither expression describes arbitrary arrangements of a's and b's. The expression does: each repetition chooses either symbol independently.
To form a pattern, translate each requirement before combining them. “Begin with a, then at least one b or c, then optionally d” becomes . The group permits a different choice on each repetition, so abccd is valid. ad is invalid because the middle group must occur at least once; abdd is invalid because d is optional once, not repeated.
Another language consists of one or more occurrences of either the pair ab or the pair ba. Its expression is . abba is valid because it is ab followed by ba; aba is invalid because the final a does not form a complete pair. Grouping is a logical part of the solution, not decorative punctuation. Other metacharacters used in an examination question will be explained there.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account