解释有限和无限语言的构造?
首先,让我们了解无限语言,然后了解如何在计算理论(TOC)中构建有限和无限语言。
无限语言
无限语言中任何字符串的长度都没有限制。
用于推导字符串的推导步骤的数量也没有限制。
例如,如果文法有n个产生式,那么任何由n+1个步骤组成的推导都会使用某个产生式两次。
如果说语言是无限的,那么必须重复使用某些产生式或产生式序列来构造推导
例子
无限语言{anb|n>0}由文法描述,
S→b|作为。
要推导字符串anb,请重复使用产生式S→aSn次,然后使用产生式S→b停止推导。
产生式S→aS允许我们说
“如果S推导出p,那么它也推导出ap。”
构造语法
让我们了解如何为无限语言构造语法。
没有通用的方法可以找到无限语言的语法,所以我们需要思考。但是,组合语法的方法可能很有用。
例子
找到以下简单语言的语法-
{∧,a,aa,...,一个,。..}={an:n∈N}
解决方案
终端集−T={a},
唯一的非终结符开始符号S,
生产规则集-
S→∧,S→aS
为有限语言构造文法
现在,我们遇到了为给定语言寻找语法的相反问题。
有时很难甚至不可能为给定的语言写下语法。此外,毫不奇怪,一种语言可能有多个语法。
如果一种语言中字符串的数量是有限的,那么对于该语言中的每个字符串w,一个文法可以由S→w形式的所有产生式组成。
例子
有限语言{a,ba}可以用下面给出的语法来描述-
S→一个|巴