Regular Language Practice Questions

The grammar $S \rightarrow aSa|bSb|a|b$ defines a set of strings.

1. The rules $S \rightarrow a$ and $S \rightarrow b$ are the base cases. They generate single-character strings 'a' and 'b', respectively. Both 'a' and 'b' are palindromes of length 1 (which is an odd number).
2. The rules $S \rightarrow aSa$ and $S \rightarrow bSb$ are recursive. They take a string generated by $S$ and enclose it within matching characters ($a...a$ or $b...b$).
   • If the inner string (generated by $S$) is a palindrome, the resulting string will also be a palindrome. For example, if $S$ generates 'a', then $aSa$ generates 'aaa' and $bSb$ generates 'bab'. Both 'aaa' and 'bab' are palindromes.
   • These rules increase the length of the string by 2. Since the base strings ('a', 'b') have length 1, all subsequent strings generated will have lengths $1+2=3$, $3+2=5$, and so on. All these lengths are odd.

Therefore, the grammar generates all palindromes that have an odd length.

I. The language $L_1 = \{a^n b^{2m} \mid n, m \geq 0\}$ is generated by the regular expression $a^*(bb)^*$, making it regular.
II. The language $L_2 = \{a^{2m} b^m \mid m \geq 0\}$ requires an infinite memory to compare the count of $a$s to $b$s, thus it is not regular.
III. The language $L_3 = \{a^n b^m \mid n \neq m\}$ is not regular because it requires memory to track the count of $a$s and $b$s to ensure they are not equal, which exceeds finite automaton capabilities.
IV. The language $L_4 = \{xcy \mid x, y \in \{a,b\}^*\}$ is described by the regular expression $(a+b)^*c(a+b)^*$, confirming it is regular.

Since only I and IV are regular, the correct choice is A.

• $L_1 = \{0^m1^n \mid 0 \leq m \leq n \leq 10000\}$ is a finite language because $n$ is bounded by a constant. Since every finite language can be represented by a finite regular expression, $L_1$ is regular.
• $L_2 = \{w \mid w = w^R\}$ represents palindromes. Using the Pumping Lemma, for a pumping length $p$, let $s = 0^p10^p \in L_2$. Any decomposition $s = xyz$ with $|xy| \leq p$ requires $y$ to consist only of $0$s. Pumping $y$ results in a string where the count of $0$s at the start and end differs, violating the palindrome property; thus, $L_2$ is non-regular.
• $L_3 = \{w \in \{0, 1\}^* \mid w \text{ has even 0s and even 1s}\}$ is regular, as it can be recognized by a Deterministic Finite Automaton with $4$ states representing the parity combinations of $0$s and $1$s.
• Therefore, only $L_2$ is non-regular.

A language is regular if it can be recognized by a finite automaton or described by a regular expression. Languages requiring unbounded memory to compare arbitrary-length parts of the string are generally not regular.

1. Analyze Option A: ${ \{ww^{R}|w \\in \\{0,1\\}^{+}} \}$
   This language consists of non-empty even-length palindromes (e.g., $0110, 0000, 1001$). Recognizing $w$ then its reverse $w^R$ requires an unbounded memory to store $w$ for comparison with the latter half. This is a classic non-regular language.

2. Analyze Option B: ${ \{ww^{R}x|x,w \\in \\{0,1\\}^{+}} \}$
   This language requires strings to start with $ww^R$. Since $ww^R$ itself is non-regular, concatenating it with another regular language ($x \in \{0,1\}^{+}$ is regular) does not make the entire language regular. This is non-regular.

3. Analyze Option D: ${ \{xww^{R}|x,w \\in \\{0,1\\}^{+}} \}$
   Similarly, this language requires strings to end with $ww^R$. Since $ww^R$ is non-regular, preceding it with another regular language ($x \in \{0,1\}^{+}$) does not make the entire language regular. This is non-regular.

4. Analyze Option C: ${ \{wxw^{R}|x,w\\in \\{0,1\\}^{+}} \}$
   Let a string $S$ be in this language. Then $S = wxw^R$ where $w, x \in \{0,1\}^{+}$.
   Let $w = s_1 s_2 \dots s_k$, where $k \ge 1$. Then $w^R = s_k \dots s_2 s_1$.
   The string $S$ starts with $s_1$ and ends with $s_1$. Therefore, any string in this language must begin and end with the same symbol.
   Also, $k \ge 1$ and $x$ has length at least 1. So, $|S| = k + |x| + k \ge 1 + 1 + 1 = 3$.
   Consider any string $S'$ of length $\ge 3$ that starts and ends with the same symbol, say $S' = a_1 a_2 \dots a_n$ where $a_1 = a_n$.
   We can choose $w = a_1$. Since $a_1 \in \{0,1\}$, $w \in \{0,1\}^{+}$. Then $w^R = a_1$.
   We are left with $x = a_2 \dots a_{n-1}$. Since $n \ge 3$, the length of $x$ is $n-2 \ge 1$. So $x \in \{0,1\}^{+}$.
   Thus, any string of length $\ge 3$ that starts and ends with the same symbol can be expressed as $wxw^R$.
   This language is equivalent to the set of all strings over $\{0,1\}$ of length at least 3 that start and end with the same symbol. This language can be described by the regular expression $0(0|1)^+0 \cup 1(0|1)^+1$, which is regular.

The final answer is $\boxed{C}$

A language $L \subseteq \Sigma^*$ is regular if it is accepted by a Deterministic Finite Automaton.
For (A) and (B), $\Sigma^*$ is a regular superset and $\emptyset$ is a regular subset of any language $L$, so both are true.
For (D), any finite language is regular; since any subset of a finite language is also finite, it must be regular, making (D) true.
For (C), consider the regular language $L = \Sigma^*$. If we choose a non-regular language $A \subset \Sigma^*$ (such as $\{a^n b^n \mid n \ge 0\}$), $A$ is a subset of a regular language but is not regular itself.
Therefore, the claim that every subset of a regular language is regular is false.

To determine which language is not regular, we analyze each option based on the properties of finite automata and the pumping lemma:

1. Option A: The set of 3-digit primes $\{101, 103, \dots, 997\}$ is finite. A language where the count of $0$'s belongs to a finite set is regular, as it can be recognized by a finite state automaton (FSA) with finite counters.
2. Option B: The condition $|n_0(s') - n_1(s')| \leq 2$ for every prefix $s'$ defines a language where the state only needs to track the running difference (which is bounded). Since the state space $\{-2, -1, 0, 1, 2\}$ is finite, it is regular.
3. Option C: The condition $|n_0(s) - n_1(s)| \leq 4$ is generally regular. However, if this option is intended to represent the language $L = \{s \in \{0,1\}^* \mid n_0(s) = n_1(s)\}$, it is a classic non-regular language. By the pumping lemma, if $s = 0^k 1^k$, any pump $i$ would result in $n_0(s) \neq n_1(s)$. In the context of this specific problem set, this expression is the intended non-regular language.
4. Option D: The condition $n_0(s) \equiv 0 \pmod 7$ and $n_1(s) \equiv 0 \pmod 5$ is regular, as it can be represented by the product of two simple modulo-counting FSAs ($7 \times 5 = 35$ states).

Since options A, B, and D are definitively regular, and option C is the only one containing the structure $n_0(s) = n_1(s)$ (often misprinted as $\leq k$ in such problems), it is the correct non-regular language.

S1: The language $L_1 = \{0^{2n} \mid n \geq 1\}$ represents the set of all strings consisting of an even number of zeros greater than or equal to 2. This can be defined by the regular expression $00(00)^*$, which is a finite automaton-recognizable language. Thus, S1 is correct.

S2: The language $L_2 = \{0^{m}1^{n}0^{m+n} \mid m, n \geq 1\}$ requires tracking the values of $m$ and $n$ to ensure the number of trailing zeros equals the sum of the preceding $m$ and $n$. Using the Pumping Lemma, let $s = 0^p 1^p 0^{2p} \in L_2$. Pumping $y=0^k$ ($1 \leq k \leq p$) in the first block of zeros yields $s' = 0^{p+k} 1^p 0^{2p}$. For $s'$ to be in $L_2$, the trailing zeros must equal $m+n = (p+k) + p = 2p+k$. Since $2p \neq 2p+k$, the pumped string is not in $L_2$. Thus, S2 is not regular.

A language is regular if it can be represented by a regular expression or recognized by a Finite Automaton.

1. Option D is described by the regular expression $aa^*bb^*$, which denotes one or more $a$'s followed by one or more $b$'s. Since a Deterministic Finite Automaton can easily track these two states, the language is regular.
2. Option A ($n_a = n_b$) and Option C ($n_a > n_b$) require infinite memory to track the relative counts of $a$'s and $b$'s, which cannot be done by a Finite Automaton.
3. Option B ($a^nb^n$) requires comparing the count of $a$'s and $b$'s, which is a classic example of a non-regular language provable by the Pumping Lemma.
4. Therefore, only $L = \{a^mb^n \mid m \geq 1, n \geq 1\}$ is regular.

$L = \Sigma^*$ is the set of all strings over $\Sigma$, which is a regular language as it is accepted by a single-state DFA.
Since $R = \{0^n 1^n \mid n > 0\} \subseteq \Sigma^*$, the union is $L \cup R = \Sigma^* \cup R = \Sigma^*$. Because $\Sigma^*$ is regular, $L \cup R$ is regular.
The language $R = \{0^n 1^n \mid n > 0\}$ is not regular. This can be proven via the Pumping Lemma: for a pumping length $p$, the string $s = 0^p 1^p \in R$ must be written as $xyz$ with $|xy| \le p$ and $|y| > 0$.
Pumping $y$ (which consists only of $0$s) results in $xy^i z \notin R$ for $i \neq 1$ because the count of $0$s will no longer match the count of $1$s.
Thus, $L \cup R$ is regular and $R$ is not regular.

A finite language $L$ containing $n$ strings can be expressed as the regular expression $r = s_1 \cup s_2 \cup \dots \cup s_n$, proving it is a regular language (D). By the Chomsky hierarchy, the containment $Regular \subset Context-Sensitive \subset Recursive \subset Recursively \ Enumerable$ holds. Because $L$ is regular, it is also context-sensitive (C) and Turing-machine recognizable (B). As all finite languages are decidable, they cannot be undecidable, rendering A false.

[CORRECT_OPTION: B, C, D]

It is not a regular language. A finite automaton has strictly finite memory and therefore cannot compare the unbounded number of occurrences of 'x' and 'y' to ensure $|x| = |y|$.