GATE CS 1995 Q1.9 — Regular Expressions and Finite Automata

According to the problem definition, an identifier must satisfy the following rules:

1. It must start with a letter ($L$).
2. The starting letter must be followed by any number of letters or digits.

Let's translate these rules into a regular expression:

• The set of letters is denoted by $L$.
• The set of digits is denoted by $D$.
• "Letters or digits" represents the union of the two sets, which is written as $(L + D)$.
• "Any number of" means zero or more occurrences, which is represented by the Kleene star ($*$). Thus, "any number of letters or digits" is $(L + D)^*$.

Combining these two parts, we get the regular expression for an identifier:

Let's evaluate the given options:

• Option A: $(L + D)^+$ – This allows an identifier to start with a digit, which is invalid.
• Option B: $(L.D)^*$ – This only allows alternating sequences of letters and digits, and also allows the empty string, which is invalid.
• Option C: $L(L + D)^*$ – This correctly matches a letter followed by any sequence of letters and/or digits.
• Option D: $L(L.D)^*$ – This restricts the characters following the first letter to only alternating letter-digit pairs.

Therefore, the correct option is C.