Exams › GATE › Technical

Let Σ = {a,b,c}. For x ∈ Σ*, and α ∈ Σ, let #α(x) denote the number of occurrences of α in x. Which one or more of the following option(s) define(s) regular language(s)?

1. {a^m bⁿ | m,n ≥ 0}
2. {a,b}* ∩ {a^m bⁿ c^(m−n) | m ≥ n ≥ 0}
3. {w | w ∈ {a,b}*, #a(w) ≡ 2 (mod 7), and #b(w) ≡ 3 (mod 9)}
4. {w | w ∈ {a,b}*, #a(w) ≡ 2 (mod 7), and #a(w) = #b(w)}

Correct answer: {w | w ∈ {a,b}*, #a(w) ≡ 2 (mod 7), and #b(w) ≡ 3 (mod 9)}

Solution

Option C defines a regular language because it specifies constraints on the counts of 'a' and 'b' using modular arithmetic, which can be represented by finite automata. Regular languages can handle such conditions, as they can track a finite number of states corresponding to the remainders of the counts.

Related GATE Technical questions

• Which one of the following options is correct for the given data in the table? Iteration (i): 0, 1, 2, 3 Input (I): 20, -4, 10, 15 Output (X): 20, 16, 26, 41 Output (Y): 20, -80, -800, -12000
• Consider a binary tree T in which every node has either zero or two children. Let n > 0 be the number of nodes in T. Which ONE of the following is the number of nodes in T that have exactly two children?
• Let L, M, and N be non-singular matrices of order 3 satisfying the equations L² = L⁻¹, M = L⁸ and N = L². Which ONE of the following is the value of the determinant of (M - N)?
• Let P(x) be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?
• Consider the following statements: (i) Address Resolution Protocol (ARP) provides a mapping from an IP address to the corresponding hardware (link-layer) address. (ii) A single TCP segment from a sender S to a receiver R cannot carry both data from S to R and acknowledgement for a segment from R to S. Which ONE of the following is CORRECT?
• A machine receives an IPv4 datagram. The protocol field of the IPv4 header has the protocol number of a protocol X. Which ONE of the following is NOT a possible candidate for X?

⚔️ Practice GATE Technical free + battle 1v1 →