IS CS-2024S-01

题目来源：Problem 1 日期：2024-08-16 题目主题：CS-Formal Languages-Finite Automata and Regular Languages

解题思路

1. NFA Construction: For the language $L_3$, we’ll design a non-deterministic finite automaton (NFA) that ensures the third symbol from the end is ‘a’.
2. Regular Expression: We will describe the general language $L_k$ using regular expressions, expressing the constraint on the $k$-th symbol from the last being ‘a’.
3. Regularity of $L^{\prime }$: We will determine whether the union of languages $L_{k^2}$ for $k\ge 1$ is regular or not, using the pumping lemma as a tool.
4. DFA State Count: We will prove that any deterministic finite automaton (DFA) accepting $L_k$ must have at least $2^k$ states by analyzing the state requirements to differentiate between possible suffixes of strings in the language.

Solution

Question 1: Non-deterministic Finite Automaton for $L_3$

To construct an NFA that accepts $L_3$, we need to ensure that the third symbol from the end is ‘a’. Here is the NFA:

• States: $q_0,q_1,q_2,q_3$
• Alphabet: $\Sigma =\{a,b\}$
• Transitions:
  • From $q_0$ (start state):
    • On reading any symbol $a$ or $b$, move to $q_0$ (this loop represents reading any number of symbols at the start).
    • On reading any symbol, move to $q_1$ (non-deterministically guess that we might be three symbols away from the end).
  • From $q_1$:
    • On reading any symbol $a$ or $b$, move to $q_2$.
  • From $q_2$:
    • On reading any symbol $a$ or $b$, move to $q_3$ (final state).
• Final State: $q_3$

This NFA accepts a string if it non-deterministically guesses that it is three symbols away from the end, and then checks if the third-to-last symbol is ‘a’.

Question 2: Regular Expression for $L_k$

To describe $L_k$ using a regular expression:

$$L_k={\Sigma }^{\ast }a{\Sigma }^{k-1}$$

Here, ${\Sigma }^{k-1}$ represents any string of length $k-1$, followed by the symbol ‘a’, and then followed by any string of arbitrary length. This ensures that the $k$-th symbol from the end is ‘a’.

Question 3: Is $L^{\prime }={\bigcup }_{k=1}^{\infty }{L}_{k^2}$ a regular language?

Claim: The language $L^{\prime }={\bigcup }_{k=1}^{\infty }{L}_{k^2}$ is not a regular language.

Proof:

To prove that $L^{\prime }$ is not a regular language, we will use the pumping lemma. The pumping lemma states that if a language is regular, then any sufficiently long string in the language can be “pumped” — that is, a portion of the string can be repeated multiple times, and the resulting strings will still belong to the language.

String Selection

Let’s consider a string $w$ carefully crafted to belong to $L_{k^2}$ for some integer $k$. For example, consider the string:

$$w=b^{k^2-1}a{b}^{k^2-1}$$

This string belongs to $L_{k^2}$ because the $k^2$-th symbol from the end is ‘a’, and all other characters are ‘b’.

Pumping Lemma Application

Assume that $L^{\prime }$ is a regular language. Then by the pumping lemma, there exists a pumping length $p$ such that any string $w$ with length at least $p$ can be decomposed as $w=xyz$, where:

• $|xy|\le p$,
• $|y|>0$, and
• $x{y}^{i}z\in L^{\prime }$ for all $i\ge 0$.

Given that $|xy|\le p$, the substring $xy$ is confined to the first $k^2$ characters, which consist entirely of ‘b’s followed by a single ‘a’ and another some ‘b’s. Thus, the substring $y$ consists of only ‘b’s (say $y=b^m$ for some $m>0$).

Pumped String

Consider the string $w^{\prime }=x{y}^{2}z$. After pumping, the string becomes:

$$w^{\prime }=b^{k^2-1}a{b}^{k^2-1+m}$$

Here, the block of ‘b’s after the ‘a’ has increased by $m$, shifting the position of the ‘a’ forward by $m$ positions. The length of $w^{\prime }$ is now greater than $w$ by $m$.

Why $w^{\prime }$ May not Belong to Any $L_{i^2}$

• Original Position: In the original string $w$, the ‘a’ was exactly at the $k^2$-th position from the end.
• New Position: After pumping, in $w^{\prime }$, the ‘a’ is now at the $(k^2+m)$-th position from the end.

For $w^{\prime }$ to belong to any $L_{i^2}$, the position of ‘a’ from the end should be exactly $i^2$ for some integer $i$. However:

• For $\forall m\in (0,2k+1)$, $k^2<k^2+m<(k+1{)}^2$, meaning that $k^2+m$ may not be a perfect square number, so $w^{\prime }$ does not always belong to any $L_{i^2}$.
• Therefore, the string $w^{\prime }\notin L_{i^2}$ for any $i$.

Question 4: Minimum Number of States in a DFA for $L_k$

Claim: Any DFA that accepts $L_k$ must have at least $2^k$ states.

Proof:

Consider the DFA accepting $L_k$. This DFA must remember the last $k$ symbols it has seen in order to determine whether the $k$-th symbol from the end is ‘a’.

There are $2^k$ possible sequences of $k$ symbols over the alphabet $\Sigma =\{a,b\}$, and the DFA must distinguish between each of these sequences because each sequence can determine whether the current string belongs to $L_k$. Thus, the DFA must have a unique state for each possible sequence of $k$ symbols.

Therefore, the DFA must have at least $2^k$ states to correctly accept all strings in $L_k$.

知识点

NFADFA正则语言泵引理

语言的取并操作

重点词汇

• NFA: 非确定性有限自动机
• DFA: 确定性有限自动机
• Pumping Lemma: 抽象引理
• Regular Expression: 正则表达式

参考资料

1. “Introduction to the Theory of Computation” by Michael Sipser, Chap. 1, 2
2. “Automata Theory, Languages, and Computation” by Hopcroft, Motwani, and Ullman, Chap. 2