鄂登引理

形式語言理論中,Ogden 引理提供了在上下文無關語言泵引理上靈活性的擴展。

基本介紹

  • 中文名:鄂登引理概述  
  • 學科:計算機
簡介,形式語言,上下文無關語言,泵引理,

簡介

形式語言理論中,Ogden 引理提供了在上下文無關語言泵引理上靈活性的擴展。
Ogden 引理聲稱如果語言L是上下文無關的,則存在某個數p> 0 (這裡的p可以是也可以不是抽吸長度),使得對於L中任何長度至少p字元串w,和“標記”p或更多個w中的位置的所有方式,w可以被寫為
  • w=uvxyz
帶有字元串u,v,x,yz,使得vy有至少一個標記了的位置,vxy有最多p個標記了的位置,而
  • uvxyzL中,對於所有i≥ 0。
Ogden 引理可以在上下文無關語言泵引理不充分的情況下,被用來證明特定語言不是上下文無關的。一個例子是語言 {abcd:i= 0 或j=k=l}。
觀察到在所有位置都被標記了的時候,這個引理等價於上下文無關語言的泵引理。

形式語言

數學邏輯計算機科學中,形式語言(英語:Formal language)是用精確的數學或機器可處理的公式定義的語言。
語言學中語言一樣,形式語言一般有兩個方面:語法語義。專門研究語言的語法的數學和計算機科學分支叫做形式語言理論,它只研究語言的語法而不致力於它的語義。在形式語言理論中,形式語言是一個字母表上的某些有限長字元串集合。一個形式語言可以包含無限多個字元串。

上下文無關語言

上下文無關語言是可以用上下文無關文法定義的形式語言。所有上下文無關語言的集契約一於下推自動機所接受的語言的集合。

泵引理

可計算性理論中的形式語言理論中,泵引理聲稱給定類的任何語言可以被“抽吸”並仍屬於這個類。一個語言可以被抽吸,如果在這個語言中任何足夠長的字元串可以分解成片段,其中某些可以任意重複來生成語言中更長的字元串。這些引理的證明典型的需要計數論證比如鴿籠原理
兩個最重要例子是正則語言的泵引理上下文無關語言的泵引理鄂登引理是另一種更強的上下文無關語言的泵引理。
這些引理可以用來確定特定語言在給定語言類中。但是它們不能被用來確定一個語言在給定類中,因為滿足引理是類成員關係的必要條件,但不是充分條件。
泵引理是1961年由Y. Bar-Hillel、M. Perles和E. Shamir首次發表的。

相關詞條

熱門詞條

聯絡我們