Regular Expressions

Definition

A regular expression (regex) is a formal notation describing a set of strings (a regular language) — used to specify token patterns for the lexer.

Key Points — Operations

• Union (a|b): matches a OR b
• Concatenation (ab): matches a followed by b
• Kleene closure (a*): zero or more repetitions of a
• Positive closure (a+): one or more repetitions
• Optional (a?): zero or one occurrence
• Regular definitions: naming sub-expressions for reuse, e.g. digit → 0|1|...|9, num → digit+

Example

• Identifier: letter (letter | digit)*
• Unsigned integer: digit+
• C-style comment: /* (any char)* */ (needs care to avoid greedy over-match)

📌 CSS Frequency: Moderate-high — often a "write a regex for..." numeric-type question (e.g., regex for a valid email, identifier, or binary string divisible by 3).

Model Answer (short)

"A regular expression is built from union, concatenation, and Kleene closure over an alphabet, and it precisely specifies token patterns for a lexer. For example, the identifier pattern letter(letter|digit)* matches any string starting with a letter followed by letters or digits — exactly what a compiler needs to recognize variable names."

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2016 · Paper-I · Q8(c) · 5 marks

Q. Lexical analysis: consider r1 = (A | … | Z) (0 | … | 9). Describe the language of r1 in English. Turn r1 into an equivalent finite automaton. Remove ε-moves.

Ans.

• Language: all strings made of zero or more capital letters followed by zero or more digits (the empty string, ABC, 123, AB12), but never a digit followed by a letter.
• NFA with ε-move: q0 (start) loops on A–Z; an ε-move goes to q1; q1 loops on 0–9; q1 is the accepting state.
• After removing ε-moves:

• Method: copy q1's outgoing moves to q0, and make q0 accepting because its ε-closure contains the final state.

2022 · Paper-I · Q8(b) · 6 marks

Q. Write a regular expression over Σ = {0, 1} for the strings that begin with 101 and end with 110.

Ans.

• 101 (0 | 1) 110*
• Overlap case: the string 10110 also begins with 101 and ends with 110 (they share a character), so a complete answer is 101(0|1)*110 | 10110.

2024 · Paper-I · Q8 · 20 marks (5 each)

Q. Write regular expressions for: (I) dates such as 10.03.2024 | 12/30/2023 | 01/01/2022, (II) a URL such as http://example.edu.pk, (III) an IP address such as 192.168.0.1, (IV) an email address such as abc@example.com.

Ans.

• I. Date (mm.dd.yyyy or mm/dd/yyyy):

^(0[1-9]|1[0-2])[./](0[1-9]|[12][0-9]|3[01])[./][0-9]{4}$

• II. URL:

^https?://([A-Za-z0-9-]+\.)+[A-Za-z]{2,}(:[0-9]+)?(/\S*)?$

• III. IPv4 address (each part 0–255):

^((25[0-5]|2[0-4][0-9]|1[0-9]{2}|[1-9]?[0-9])\.){3}(25[0-5]|2[0-4][0-9]|1[0-9]{2}|[1-9]?[0-9])$

• IV. Email:

^[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,}$

• Notes: ^ and $ anchor the whole string, [ ] is a character class, {n} is a count, ? means optional, and | means or.

2025 · Paper-I · Q8(a) · 6 marks

Q. Create a regular expression for the language that always starts with the string "baa", and draw the DFA with an explanation of each step.

Ans. (Alphabet Σ = {a, b}.)

• Regular expression: baa (a | b)*
• DFA steps:
  • q0 (start): needs b first, otherwise go to the dead state
  • q1: has read b, needs a
  • q2: has read ba, needs a
  • q3 (accepting): has read baa, then accepts any further a or b (loops)