标签: regular-language

在我接受的CS课程中,有一个不常规的语言示例:

{a^nb^n | n >= 0}

我可以理解它不常规,因为没有有限状态自动机/机器可以编写验证和接受此输入,因为它缺少一个内存组件.(如果我错了,请纠正我)

关于常规语言的维基百科条目也列出了这个例子,但没有提供(数学)证明为什么它不常规.

任何人都可以启发我并为此提供证据,或者指出我太好的资源？

我在解决这个问题时遇到了问题: - 它是一个任务,我解决了它,但它看起来太长而且模糊,可以帮助我,请帮助我......

具有偶数个a和奇数个b的字符串的正则表达式,其中字符集= {a,b}.

我无法阐明Chomsky类型2(无上下文语言)和Chomsky类型3(常规语言)之间的区别.

有人可以用简单的英语给我一个答案吗？我无法理解整个层次结构的事情.

顾名思义,我们可能认为正则表达式只能匹配常规语言.但是我们在实践中使用的正则表达式包含的东西我不确定它们是否可以与理论对应物一起实现.例如,如何模拟反向引用？所以问题出现了:我们在实践中使用的正则表达式的理论力量是什么？你能想出一种匹配方式{(a^n)(b^n)|n>=0}吗？怎么样{(a^n)(b^n)(c^n)|n>=0}？

例如,在给我的作业中,我们被要求查明两个正则表达式是否相等.

(a+b+c)*  and ((ab)**c*)*

我的问题是如何做到这一点？如果我绘制两者的转换图,然后通过它运行几个字符串并显示两个TG都能够接受它,这是否足以证明？如果没有,我该怎么办？对此有一种数学/公理方法吗？

提前致谢.

编辑:还有一件事我想清楚哪一点与这个问题有关.下面照片中描绘的两个FA是否相同？

即上图中的(1)和(2)是否相同？

我们知道,给定一个常规语法,我们有算法来获得它的正则表达式.

但是如果给定的语法是无上下文语法(但它只生成常规语言),就像

我正在学习 Linux 上的 sed s/regexp/replacement/ 命令。

phone.txt 中有一些号码

(555)555-1212
(555)555-1213
(555)555-1214
(666)555-1215
(777)555-1217

我想使用正则表达式（我已经在https://www.freeformatter.com/regex-tester.html上测试过）

 (\(555\))(.*-)(.*$)

匹配以 (555) 开头的数字。然后我希望这些匹配数字的这三个部分的输出为：（数字 (555)555-1212 的示例）

Area code: (555) Second: 555- Third: 1212

我尝试了以下命令：

cat phone.txt | sed 's/\(\\\(555\\\)\)\(.*-\)\(.*$)/Area code: \1 Second: \2 Third: \3/'

但系统给了我：

sed: -e expression #1, char 66: Unmatched ( or \(

所有数字的通用命令是：

cat phone.txt | sed 's/\(.*)\)\(.*-\)\(.*$\)/Area code: \1 Second: \2 Third: \3/'

来源： https: //www.tutorialspoint.com/unix/unix-regular-expressions.htm

但我只想对以 (555) 开头的数字执行 sed ，并通过后向引用将其添加到输出中。

你能告诉我如何正确地编写这个特殊命令吗？

所以这不是关于泵浦引理及其工作原理,而是关于先决条件.

你可以阅读网络中的任何地方,常规语言必须通过抽取引理,但现在任何人都会谈论有限语言,它实际上是常规语言的一部分.

所以我们可能都是aggree,以下语言是有限语言,也是常规语言,但它肯定不会通过泵引理:

L = {'abc', 'defghi'}

请告诉我,如果没有人写它或为什么我们错了 - 甚至没有.

我正在阅读正则表达式解析器的代码,并开始怀疑正则表达式的语法本身是否是常规的,并且可以用另一个(非常复杂的)正则表达式表达？

rere = "" # the regular expression of regular language
match1 = re.match(rere, "[a-z]+@[a-z]+.com") # True
match2 = re.match(rere, ")az[") # False 

我没有在正则表达式语法中看到任何递归结构,所以我想也许这是可行的？

如果是,表达式是什么样的？如果没有,为什么？

以下语言的最小抽水长度是多少？

1. 空语
2. (01)*
3. 10(11*0)*0
4. 1011
5. 011 ü 0*1*

这是我的解决方案.如果我错了,请纠正我.

1. p = 0,因为该语言没有可泵送的字符串
2. p = 2因为01是可以泵送的最短字符串
3. p = 5因为10100是可以泵送的最短字符串
4. p = 0,因为不能抽出字符串
5. p = 1,因为0可以泵送字符串

我不确定我的答案,所以任何帮助都表示赞赏.非常感谢!