如何在 TOC 中识别语言是否为正则语言？

判断一种语言是否为正则语言，是基于鸽巢原理的。这通常被称为泵浦引理。

正则语言的泵浦引理

• 它提供了一种从给定字符串中“泵出”（生成）许多子串的方法。

• 换句话说，它提供了一种将给定的长输入字符串分解成多个子串的方法。

• 它给出了证明一组字符串不是正则语言的必要条件。

但是泵浦引理是一个反证法测试。这意味着如果任何语言不满足泵浦引理，那么我们可以说它不是正则语言。但是，如果它满足条件，那么我们可以说该语言可能是也可能不是正则语言。

泵浦引理是一个数学证明，需要更多时间，有时也会造成很多困惑。

每种有限语言都是正则语言，这意味着如果语言有限，那么我们可以说它是正则语言。

例如，考虑下面给出的语言：

       L = { a¹⁰b²⁰} 是正则语言，而

       L = { aⁿbⁿ| n > 0} 不是正则语言。

假设，如果存在无限语言，我们将检查是否可以创建其确定性有限自动机 (DFA)。如果我们无法创建，则它不是正则语言。

字符串长度呈算术级数递增，并且语言中应该存在某种模式，否则无法创建有限自动机 (FA)。

让我们考虑一些例子来识别语言是否为正则语言

每个有限集都表示一个正则语言。

示例 1

让我们考虑在字母表 {a, b}* 上所有长度为 2 的字符串。

则语言如下所示，并且是正则的：

       L = {aa, ab, ba, bb}。

在上题中，给出了在 {a, b}* 上所有长度为 2 的字符串的表达式，这是一个非正则语言，但其值受某个常数（例如长度 2）限制。因此，我们可以说该语言是正则的。这可以通过反证法来证明。

示例 2

找出语言 L = {aⁿ | n ≥1} 是否为正则语言。

如果我们仔细观察给定的问题，该语言中存在某种模式，并且可以为该语言生成 FA。因此，我们可以说给定的语言是正则语言。

给定语言的 DFA 如下：

Bhanu Priya

更新于：2021年6月12日

5K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习