Table of Contents
hide
Regular Language(RL)
- A regular language is any set of strings over a finite alphabet (Σ) that can be accepted or recognized by a finite automaton (DFA or NFA).
- Regular languages are the simplest class of languages in the Chomsky hierarchy of formal languages, a concept within the Theory of Computation (TOC).
- A regular language can be created or represented by:-
- Regular Grammar
- Regular Expression
- Finite Automaton (DFA/NFA)
- For example –
- All strings of 0s and 1s ending in 01 (like 101, 0001), or even-length binary strings.
- Properties of Regular Language
- Closure Properties: Regular languages are closed under union, concatenation, star, intersection, complement, and difference.
- Pumping Lemma: For any regular language L, there exists p (pumping length) such that any string w ∈ L with |w| ≥ p can be divided as xyz where |xy| ≤ p, |y| > 0, and xy^k z ∈ L for all k ≥ 0. It is used to prove non-regularity (e.g., {0^n 1^n | n ≥ 0} is not regular).
- Equivalence: Regular languages ↔ Regular Expressions ↔ DFAs ↔ NFAs ↔ Regular Grammars
Regular Expressions
- A Regular Expression is a formal notation used to describe or represent regular languages.
- It defines patterns of strings over an alphabet.
- Every regular expression defines a regular language, and every regular language can be expressed using a regular expression.
- Properties of Regular Expressions
- Empty string(ε)
- Empty set/language(∅)
- Literal (a ∈ Σ)
- Union/OR(∪ or | or +): R1 ∪ R2 matches strings in either R1 or R2 (e.g., (a|b) matches “a” or “b”).
- Intersection
- Complement
- Concatenation(·): R1 · R2 matches R1 followed by R2 (e.g., ab matches “ab”).
- Kleene star(*): R* matches zero or more repetitions of R (e.g., a* matches ε, a, aa, aaa…).
Use/Importance
- Regular languages and regular expressions form the foundation of automata theory and are widely used in programming languages, compilers, and text processing.
Example Practices
- Exmple : One or More Occurrences
- Regular expressions = a.a*/aa*
- Regular Languages(L) = {a, aa, aaa, …} : Language should have at least one first location ‘a’.
-
- Regular expressions = (aa)* = L = { ε, aa, aaaa, aaaaaa, … } = generates only even-length strings of a’s.
- Regular expressions = ab* = { a, ab, abb, abbb, abbbb, … } : b should be zero or one or more.
- Regular expressions = a*ba* = L = { b, ab, ba, aab, baa, aaab, abaa, aabaa, … } = Strings with zero or more a’s, followed by exactly one b, and then followed by zero or more a’s, i.e., Strings with exactly one b
- Regular expressions = a+b* = a+ { ε, b, bb, bbb, … } = { a } ∪ { ε, b, bb, bbb, … } =
L = { a, ε, b, bb, bbb, bbbb, … }
-
- Regular expressions = (a+b)* = L = { ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, … }
Repeat/Mixing of a or b any number of times (including zero times)/All possible strings made of a and b in any order, including ε - Regular expressions = (a*)+(b*) = Either all a’s OR all b’s = Only a’s OR only b’s = No mixing of a and b like (a+b)* =
a* = only a’s (or ε)b* = only b’s (or ε)+ = union (OR)L={ε,a,aa,aaa,…}∪{ε,b,bb,bbb,…} = L = { ε, a, aa, aaa, …, b, bb, bbb, … }
- Regular expressions = a*b*= {ε, a, aa, aaa, …}. {ε, b, bb, bbb, …} = { ε, a, aa, aaa, b, bb, bbb, ab, aab, aaab, abbb, aabb, … } : all a’s must come before any b’s/Any number of a’s followed by b’s
- Regular expressions = (a+b)*a = L= { a, aa, ba, aba, bba, aaba, babba, … } = Any combination of a and b, but the last character must be a.
- Regular expressions = a(a+b)* = L = { a, aa, ab, aaa, aab, aba, abb, aaba, abbb, … } = The string must begin with a and be followed by any number (including zero) of a’s and b’s in any order of (a+b)*.
- Regular expressions = (0 + 1)* = L = { ε, 0, 1, 00, 01, 10, 11, 000, 101, 1101, … }
All possible binary strings (including the empty string) formed using 0 and 1 in any order and any length, but finite. - Regular expressions = (0 + 1)*01 = L = { 01, 001, 101, 1101, 0001, 0101, 11101, … } = Set of all binary strings (made of 0s and 1s) that must end with 01.
- Regular expressions = (a + b)(a + b)* = (a + b)+ = L = { a, b, aa, ab, ba, bb, aaa, aab, aba, … } =
(a + b) means exactly one symbol, either a or b, and (a + b)* means zero or more symbols, each either a or b = At least one symbol from {a, b}, followed by any number of symbols from {a, b} = represents all non-empty strings over the alphabet {a, b}.
- Regular expressions = (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)+ = L= 0, 5, 12, 789, 2025 =
Strings of one or more digits (positive integers)
- Regular expressions = (a+b)* = L = { ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, … }
0 Comments