如何在 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+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習