pet*_*bel 1 grammar context-free-grammar automaton exponential context-free-language
我是那种一卡与自动机和语法问题.我搜索了很多但没有成功.
它甚至有可能构建一个语法生成这种语言L？
L = { a(2i) | i >= 0}
谁能为我提供简单的解决方案？
为这种语言写一个语法肯定是可能的,但它不会是一个无上下文的语法.使用泵浦引理很容易证明这一点.
抽取引理表明,对于任何CFL,都有一些整数p,使得s语言中的长度至少p可以写为uvxyz,where u,v和x,y并且z是字符串vy且不为空,并且对于所有整数n,字符串是也用语言.uvnxynz
也就是说,在语言(它的长度的任何字符串l大于p),有一些存在k使得有在其长度的语言串l + nk为任何整数n.对于该语言来说情况并非如此,因为这些字符串具有指数长度,因此语言不能无上下文.a2i
为语言构建一个非上下文无关的语法并不困难,但我不知道它有多么有用.
以下是Type 0语法(即它也不是上下文敏感的),但仅仅是因为用于删除元字符的产生.这里的基本思想是我们在字符串([和])周围放置开始和结束标记,并且我们有一个"复制器"(↣),它从左到右移动加倍a.当它击中结束标记时,它会变成后退穿梭(↢)或它吃掉终点标记并变成起始标记 - 驱逐舰(↞)
Start: [↣a]
↣a: aa↣
↣]: ↢]
↣]: ↞
a↢: ↢a
a↞: ↞a
[↢: [↣
[↞: