---
title: "Regular expressions and regular languages"
subject: "Discrete Structure"
chapter: 2
key: "semester_4/discrete_structure:regular-expressions-and-languages"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/regular-expressions-and-languages
site: BCT Engineering
---

# Regular expressions and regular languages

Discrete Structure · Chapter 2: Finite State Automata

- Asked in: 2068 Bhadra, 4 marks
- Video: [Lec-29: Regular Expressions in TOC with examples | Formal Definition](https://www.youtube.com/watch?v=rjG5LwbqAp4) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/regular-expressions-and-languages
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-2

## Question

Discuss regular expressions and regular languages in detail with suitable examples.

## Short answer

Regular expressions are built from ∅, ε, symbols, and operations +, concatenation, *. A regular language is one described by a regular expression, equivalent to acceptance by a DFA/NFA or generation by a regular grammar. Examples: a*b, (a+b)*aa(a+b)*. They are closed under union, intersection, complement, but cannot count unboundedly (e.g., {a^n b^n} is not regular).

## Answer

#### Regular expressions
Over an alphabet Σ, regular expressions are defined recursively:
1. ∅ (empty set), ε (empty string) and each symbol a ∈ Σ are regular expressions.
2. If R and S are regular expressions, so are (R + S) (union), (RS) (concatenation) and R* (Kleene closure).
3. Nothing else is a regular expression.

Meaning: L(∅) = ∅, L(ε) = {ε}, L(a) = {a}, L(R+S) = L(R) ∪ L(S), L(RS) = L(R)L(S), L(R*) = (L(R))*, where R* means zero or more repetitions (R⁺ = RR* means one or more).

#### Regular languages
A language is **regular** if it can be described by a regular expression. By **Kleene's theorem**, this is equivalent to being accepted by a DFA, an NFA, or generated by a regular (Type 3) grammar.

#### Examples

| Regular expression | Language over {a, b} |
|---|---|
| a*b | any number of a's followed by one b |
| (a+b)* | all strings, including ε |
| (a+b)*aa(a+b)* | strings containing aa |
| (a+b)*abb | strings ending in abb |
| (ab)* | ε, ab, abab, ... |
| a(a+b)*b | strings starting with a and ending with b |

#### Properties
- Regular languages are closed under union, concatenation, Kleene star, complement, intersection and reversal.
- Useful identities: R + ∅ = R, Rε = R, R∅ = ∅, (R*)* = R*, (R+S)* = (R*S*)*, ε + RR* = R*.
- Languages such as { aⁿbⁿ : n ≥ 0 } are **not** regular (a finite automaton cannot count without bound); this is shown with the pumping lemma.

#### Use
Token definition in compilers, pattern search in text, validating input, and designing finite automata.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What are the base regular expressions?
   A. Only the symbols in Σ
   B. ∅, ε and each symbol a in Σ
   C. Only ∅ and ε
   D. Σ* and ∅
   Answer: B. Union, concatenation and star are then built from them. (Key point: Base cases)

2. What does R* mean?
   A. Exactly one string of L(R)
   B. One or more repetitions
   C. Zero or more repetitions of strings from L(R)
   D. R followed by R
   Answer: C. R+ means one or more, R* includes ε. (Key point: Meaning of star)

3. What does (a+b)*aa(a+b)* describe?
   A. Strings over {a,b} containing aa
   B. Strings ending in aa
   C. Strings beginning with aa
   D. Strings with only a's
   Answer: A. Any prefix, then aa, then any suffix. (Key point: Example language)

4. Why is { a^n b^n } not regular?
   A. It is infinite
   B. A finite automaton cannot count without bound; this is shown by the pumping lemma
   C. It needs ε
   D. It contains both a and b
   Answer: B. Infinite languages can be regular; the issue is unbounded counting. (Key point: Non-regular language)

## Related in Discrete Structure

- [Role of regular expressions](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Arole-of-regular-expressions) — Discrete Structure, chapter 2
- [Closure properties of regular languages](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aclosure-properties-regular-language) — Discrete Structure, chapter 2, asked 2×

## Related in other subjects

- [Closure properties of regular languages](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aregular-closure-properties) — Theory of Computation, chapter 2, asked 2×
- [Pumping lemma: a^(n²) not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-square-not-regular) — Theory of Computation, chapter 2, asked 5×
- [Pumping lemma: aⁿb²ⁿ not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-an-b2n-not-regular) — Theory of Computation, chapter 2, asked 3×
- [Pumping lemma: aⁿbaⁿ not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-anban-not-regular) — Theory of Computation, chapter 2