Answer: True

Justification: To prove that the two regular expressions denote the same language, we show mutual subset containment:

1. $L(R_2) \subseteq L(R_1)$: $R_2 = (a \cup b)^*$ represents the set of all possible strings over the alphabet $\Sigma = \{a, b\}$. Since any language over $\Sigma$ is a subset of $\Sigma^*$, $L(R_1) \subseteq L(R_2)$ is trivially true.
2. $L(R_2) \subseteq L(R_1)$: Every string $w \in \Sigma^*$ can be partitioned into alternating runs of $a$’s and $b$’s (e.g., $w = a^{n_1}b^{m_1}a^{n_2}b^{m_2}\dots$). Each individual block $a^{n_i}b^{m_i}$ is generated by the subexpression $a^*b^*$. By applying the outer Kleene star to this subexpression, we can concatenate any finite number of these blocks. Therefore, any string in $\Sigma^*$ can be generated by $(a^*b^*)^*$, proving $L(R_2) \subseteq L(R_1)$.

Since both containment directions hold, $L((a^*b^*)^*) = L((a \cup b)^*) = \Sigma^*$.

Answer: False

Justification: By definition, the Kleene star of any language $L$ is defined as:

Where $L^0 = \{\varepsilon\}$ (the language containing only the empty string). For $L = \emptyset$, we calculate:

Thus, $\emptyset^* = \{\varepsilon\} \neq \emptyset$. The language $\{\varepsilon\}$ contains one string of length zero, whereas the language $\emptyset$ contains no strings at all.

Answer: False

Justification: By definition, a linear grammar is a grammar in which at most one variable can occur on the right-hand side of any production rule, with no restrictions on where that variable is positioned. A regular grammar must be either strictly right-linear ($A \to wB$ or $A \to w$) or strictly left-linear ($A \to Bw$ or $A \to w$).

Consider the grammar $G$ with production rules:

This grammar is linear because there is at most one variable ($S$) on the right-hand side of each production. However, it is neither right-linear nor left-linear because the variable $S$ is sandwiched between terminals $a$ and $b$. This linear grammar generates the language $L(G) = \{a^n b^n \mid n \geq 0\}$, which is context-free and non-regular, proving that not all linear grammars are regular.

Answer: False

Justification: The state-elimination update formula is defined as:

where we eliminate a single state $q_{rip}$ at a time. This sequential elimination is mathematically necessary because ripping a state updates the direct paths between all remaining active states to account for paths that previously routed through the eliminated state. Ripping multiple states simultaneously would ignore the routing feedback loops and parallel paths between those eliminated states themselves, leading to an incorrect regular expression that fails to represent the full language.

Correct Options: A, B

Justification:

• A is correct: In any string lacking $aa$, every occurrence of $a$ (except possibly one at the very end of the string) must be immediately followed by at least one $b$. We can partition such a string into blocks of $b$ and $ab$. Any concatenation of these blocks is represented by $(b \cup ab)^*$. If the string ends in an $a$, we append it at the end via $(a \cup \varepsilon)$, yielding $(b \cup ab)^*(a \cup \varepsilon)$.
• B is correct: This is the symmetric dual of Option A. Here, every $a$ (except possibly one at the very beginning of the string) must be immediately preceded by a $b$. This allows us to partition the repeating blocks into $b$ and $ba$, optionally starting with $a$, represented as $(\varepsilon \cup a)(b \cup ba)^*$.
• C is incorrect: The subexpression $(ab^*)^*$ allows us to choose $b^* = \varepsilon$, which can generate $aa$ (e.g., $(a\varepsilon)(a\varepsilon) = aa$).
• D is incorrect: This regular expression cannot generate valid strings such as $bab$ (which does not contain $aa$) because it forces all alternating $a$’s and $b$’s after the initial $b^*$ block to be grouped strictly as pairs of $ab$.

Correct Options: A, C, D

Justification: A grammar is right-linear if all production rules are of the form $A \to wB$ or $A \to w$, where $A, B \in V$ and $w \in \Sigma^*$.

• A is correct: Here, $w = ab \in \Sigma^*$ and $B \in V$.
• B is incorrect: This is a left-linear production rule ($A \to Bw$) because the variable $B$ appears to the left of the terminal string $a$.
• C is correct: Here, $w = \varepsilon \in \Sigma^*$ (a terminal string of length zero) with no variable on the right-hand side.
• D is correct: Both options ($aB$ and $b$) fit the right-linear criteria ($w = a, B = B$ and $w = b$ respectively).

1. Algebraic Analysis

If a string $w$ cannot contain the substring $110$, it means that once two consecutive $1$’s are formed (representing $11$), we can never allow a $0$ to appear later in the string. Any $0$ appearing after $11$ would complete the forbidden $110$ pattern.

This behavior allows us to divide any valid string into two main sequential phases:

1. The Alternating/Safe Phase: A phase containing any combinations of $0$’s and $1$’s, provided that we never form $11$. In this phase, every $1$ must be immediately followed by a $0$ (represented as the block $10$), or appear as an isolated $1$ at the very end of this phase. This phase can be written as: $$(0 \cup 10)^*$$
2. The Terminal Star-Phase: Once we decide to transition out of the alternating phase by writing two or more consecutive $1$’s, we enter a state where only $1$’s are allowed. This is represented simply as: $$1^*$$

Combining these two phases sequentially, we get our regular expression:

2. Verification of Correctness

• No $110$ is possible: In our expression $(0 \cup 10)^* 1^*$, the only way to generate a sequence of $1$’s of length $\geq 2$ is by using the trailing $1^*$ block. Since $1^*$ is positioned at the very end of the expression, no characters from the first block $(0 \cup 10)^*$ can be appended after it. Thus, no $0$ can ever follow a $11$ sequence, making the formation of $110$ algebraically impossible.
• Generates all valid strings: Any valid string that does not contain $110$ either:
  • Contains no $11$ anywhere: This is generated by $(0 \cup 10)^*1^*$ with $1^*$ chosen as $\varepsilon$ or a single $1$.
  • Contains a $11$: Let the first occurrence of $11$ start at index $k$. The prefix up to index $k-1$ contains no $11$ and ends in $0$ or $1$, which is generated by $(0 \cup 10)^*$. The suffix starting at $k$ must consist entirely of $1$’s, which is generated by $1^*$.

Step 1: Base Automata for Terminals

We construct the primitive NFAs for the individual terminals $a$ and $b$:

• $N_a$: $$q_a \xrightarrow{a} q_f$$
• $N_b$: $$p_b \xrightarrow{b} p_f$$

Step 2: Concatenation $ab$

To construct the NFA for $ab$, we link $N_a$ to $N_b$ using an $\varepsilon$-transition:

Let’s simplify and re-label this sequential machine $N_{ab}$ with states $\{1, 2, 3\}$:

Step 3: Union $ab \cup a$

To construct the NFA for $N_{ab \cup a}$, we introduce a new start state $s_0$ and a new accept state $f_0$. We run $N_{ab}$ and $N_a$ in parallel:

• Transitions from $s_0$:
  • $s_0 \xrightarrow{\varepsilon} 1$ (start of $ab$)
  • $s_0 \xrightarrow{\varepsilon} q_a$ (start of $a$)
• Transitions to $f_0$:
  • $3 \xrightarrow{\varepsilon} f_0$ (from accept of $ab$)
  • $q_f \xrightarrow{\varepsilon} f_0$ (from accept of $a$)

The combined state set is $\{s_0, 1, 2, 3, q_a, q_f, f_0\}$.

Step 4: Kleene Star $(ab \cup a)^*$

To construct the star closure, we introduce a brand-new start state $S$ and accept state $F$:

1. Initial transition: $S \xrightarrow{\varepsilon} s_0$
2. Loopback transition: $f_0 \xrightarrow{\varepsilon} s_0$ (allowing repetition)
3. Bypass transition: $S \xrightarrow{\varepsilon} F$ (allowing the empty string $\varepsilon$)
4. Exit transition: $f_0 \xrightarrow{\varepsilon} F$

Final Transition Table of the NFA

Step 1: Initialize the GNFA

We add a new start state $q_{start}$ and a new accept state $q_{accept}$ with $\varepsilon$-transitions:

• $q_{start} \xrightarrow{\varepsilon} q_1$
• $q_3 \xrightarrow{\varepsilon} q_{accept}$

The state graph initially contains the following transitions between active states $\{q_1, q_2, q_3\}$:

• $R_{11} = b$
• $R_{12} = a$
• $R_{22} = a$
• $R_{23} = b$
• $R_{33} = a$
• $R_{31} = b$

Step 2: Eliminate State $q_2$

We eliminate $q_2$ and update the transition labels between $q_1$ and $q_3$. The only path traveling through $q_2$ goes from $q_1$ to $q_3$:

We calculate the new label $R_{13}'$:

Since no other paths travel through $q_2$, we remove $q_2$. The remaining active states are $\{q_1, q_3\}$ with transitions:

• Loop on $q_1$: $R_{11} = b$
• Path $q_1 \to q_3$: $R_{13}' = aa^*b$
• Loop on $q_3$: $R_{33} = a$
• Path $q_3 \to q_1$: $R_{31} = b$

Step 3: Eliminate State $q_3$

We now eliminate $q_3$ to leave only $q_1$ connected to $q_{accept}$. Eliminating $q_3$ updates the loop on $q_1$ and the path from $q_1$ to $q_{accept}$:

1. Update the Loop on $q_1$ ($R_{11}''$): Ripping $q_3$ introduces a loopback path $q_1 \to q_3 \to q_1$:

   $$R_{11}'' = R_{11} \cup R_{13}'(R_{33})^*R_{31} = b \cup (aa^*b)(a)^*(b) = b \cup aa^*ba^*b$$

2. Update the path from $q_1$ to $q_{accept}$ ($R_{1,accept}'$): The path from $q_1$ to $q_{accept}$ goes through $q_3$:

   $$R_{1,accept}' = R_{13}'(R_{33})^*R_{3,accept} = (aa^*b)(a)^*(\varepsilon) = aa^*ba^*$$

Step 4: Construct the Final Regular Expression

The GNFA is now reduced to:

with a self-loop $R_{11}''$ on $q_1$.

The final regular expression is:

Part 1: Convert Right-Linear Grammar to NFA

Mapping Rules:

• Each grammar variable $V_i \in V$ maps directly to an NFA state $q_i \in Q$.
• The start variable $S$ maps to the NFA start state $q_S$.
• We introduce a designated final accepting state $q_f$.
• Production rules map to transitions:
  • $A \to aB$ maps to $\delta(q_A, a) = q_B$
  • $A \to a$ maps to $\delta(q_A, a) = q_f$
  • $A \to \lambda$ makes $q_A$ an accepting state (or maps to $\delta(q_A, \varepsilon) = q_f$)

NFA Construction:

• States $Q$: $\{q_S, q_A, q_B, q_f\}$
• Start State: $q_S$
• Accepting States $F$: $\{q_S, q_B, q_f\}$ (since $S \to \lambda$ and $B \to \lambda$)
• Transitions:
  • From $S \to aA \implies \delta(q_S, a) = \{q_A\}$
  • From $S \to bS \implies \delta(q_S, b) = \{q_S\}$
  • From $A \to aA \implies \delta(q_A, a) = \{q_A\}$
  • From $A \to bB \implies \delta(q_A, b) = \{q_B\}$
  • From $B \to aS \implies \delta(q_B, a) = \{q_S\}$

Part 2: Find Equivalent Left-Linear Grammar

To find an equivalent left-linear grammar for $L$, we use the Reversal Theorem:

1. Step 1: Reverse the Right-Linear Grammar $G$ to get $G^R$: To construct $G^R$ generating $L^R$, we reverse the terminal strings on the right-hand side of each production rule in $G$:

   • $S \to Aa \mid Sb \mid \lambda$
   • $A \to Aa \mid Bb$
   • $B \to Sa \mid \lambda$

   (Note: This is a left-linear grammar for $L^R$. We need to convert this to right-linear for $L^R$ first, then reverse it back to left-linear for $L$).

2. Step 2: Construct the NFA for $L^R$: Let’s reverse the transition arrows of our NFA from Part 1 and swap start/accept states to recognize $L^R$:

   • New Start State: $\{q_S, q_B, q_f\}$ (former accept states). To simplify, we introduce a single start state $q_0 \xrightarrow{\varepsilon} \{q_S, q_B, q_f\}$.
   • New Accept State: $q_S$ (former start state).
   • Reversed Transitions:
     • $\delta'(q_A, a) = q_S$ (from $\delta(q_S, a) = q_A$)
     • $\delta'(q_S, b) = q_S$ (from $\delta(q_S, b) = q_S$)
     • $\delta'(q_A, a) = q_A$ (from $\delta(q_A, a) = q_A$)
     • $\delta'(q_B, b) = q_A$ (from $\delta(q_A, b) = q_B$)
     • $\delta'(q_S, a) = q_B$ (from $\delta(q_B, a) = q_S$)

3. Step 3: Construct Right-Linear Grammar $G_{RL}$ for $L^R$ from the NFA:

   • $q_0 \to q_S \mid q_B \mid \lambda$ (since $q_S$ is accepting, $q_0 \to \lambda$)
   • $q_S \to b q_S \mid a q_B \mid \lambda$ (since $q_S$ is accepting)
   • $q_A \to a q_S \mid a q_A$
   • $q_B \to b q_A$

4. Step 4: Reverse $G_{RL}$ to get the Left-Linear Grammar $G_{LL}$ for $L$: We reverse the production rules of $G_{RL}$ to get our final left-linear grammar:

   • $S \to Sb \mid \lambda$
   • $A \to Aa \mid Bb$
   • $B \to Sa$
   • Start variable is $S$.