问题标签 [formal-languages]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
1133 浏览

context-free-grammar - L* 和 Σ* 之间的差异

有人可以解释和之间的确切区别Σ*,语言L*在哪里, L语言Σ的字母在L哪里?

谢谢

0 投票
4 回答
5698 浏览

math - 确保:仅为无限常规语言抽取引理?

所以这不是关于抽水引理及其工作原理,而是关于先决条件。

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

所以我们可能都同意,以下语言是一种有限语言,也是一种常规语言,但它绝对没有通过抽水引理:

L = {'abc', 'defghi'}

请告诉我是否根本没有人写它,或者我们为什么错了——甚至没有。

0 投票
1 回答
617 浏览

regex - 查找包含子字符串 01a 和字母表 {0,1,a} 中偶数个 1 的字符串的正则表达式

由其描述给出的常规语言:

{0,1, a} 的所有字符串的集合,其中包含子字符串 '01a' 和偶数个 '1'。例如,“01a1”、“101a”、“101a101”。

如何构造一个指定语言的正则表达式?

0 投票
1 回答
798 浏览

turing-machines - 有没有什么简单的方法可以解决“构建图灵机……”的问题?

我理解图灵机的逻辑。当给出图灵机时,我可以理解它是如何工作的以及它是如何停止的。但是当它被要求构建一个图灵机时,它就更加困难了。

有什么简单的方法可以找到以下问题的答案:

我想绘制这些图灵机的图表?有没有什么方法,比如填表然后画图等等?

我在网上搜索了很多关于这个主题的内容。只有答案(只有图表)。没有解释它是如何解决的。

提前致谢

0 投票
1 回答
1044 浏览

c - XML的形式语法

我试图在 C 中为 XML 文件构建小型解析器。我知道,我可以找到一些完成的解决方案,但是,我只需要一些用于嵌入式项目的基本东西。我正在尝试创建用于描述没有属性的 XML 的语法,只有标签,但它似乎不起作用,我无法弄清楚原因。

这是语法:

这是实现此语法的 C 代码的一部分:

}

编辑:这是不满足此语法的 XML 文件示例:

它在输出端给出 END EXPECTED。

0 投票
1 回答
4180 浏览

finite-automata - 非线性、明确和非确定性 CFL 的示例?

在形式语言的乔姆斯基分类中,我需要一些Non-Linear, Unambiguous and also Non-Deterministic上下文无关语言(N-CFL)的例子吗?

  1. 线性语言线性语法是可能的(⊆ CFG),例如
    L 1 = {a n b n | n≥0}

  2. 确定性上下文无关语言(D-CFG):确定性下推自动机(D-PDA)是可能的,例如
    L 2 = {a n b n c m | n ≥ 0, m ≥ 0 }
    L 2是明确的。

非线性的 CF 文法是非线性的
L nl = {w: n a (w) = n b (w)} 也是非线性 CFG

-- 3. Non-Deterministic Context Free Language(N-CFG) :only Non-Deterministic Push-Down-Automata(N-PDA)可能的例如
L 3 = {ww R | w ∈ {a, b} * }
L 3也是线性CFG。

--4。模棱两可的 CFL : only ambiguous CFG is possible
L 4 = {a n b n c m |的 CFL n ≥ 0, m ≥ 0 } U {a n b m c m | n ≥ 0, m ≥ 0 }
L 4既是非线性又是模糊 CFG 和每个模糊 CFL \subseteq N-CFL。

我的问题是:
是否所有非线性、非确定性 CFL 都是模棱两可的?如果不是,那么我需要一个非线性、非确定性 CFL 且明确的示例?

给定下面的维恩图:

在此处输入图像描述

也在这里问

0 投票
1 回答
440 浏览

email - 电子邮件地址格式的正式定义是什么?

我想知道构建电子邮件地址的正式定义。

我不只是想要答案,而是如何得到它,因为我想自己学习如何去做。

0 投票
1 回答
1173 浏览

regular-language - 抽引理(常规语言)

我需要一些帮助来解决抽水引理问题。

这是我到目前为止得到的:

我让 y = abbc^n,n 是来自抽水引理的长度。y 在 L 中是因为 a:s 的数量小于 b:s 的数量,并且 b:s 的数量小于 c:s 的数量。

我让 u = a,v = bb 和 w = c^n。|紫外线| < y,如抽水引理中所述。如果我“抽” (bb)^2 那么我得到

这是正确的吗 ?我在“正确的道路”上吗?

谢谢

0 投票
0 回答
737 浏览

context-free-grammar - 上下文无关语法 - LR(0) DFA

我需要一些帮助来为上下文无关语法构建 LR(0) DFA。

这就是我所拥有的:

状态

然后我有一个标记a为:

状态

从这个状态,一个箭头标记a为:

状态:

这就是我的问题开始的地方。正如你所看到的,我从这个状态得到两个箭头B,因为我有:

我做错了什么?

0 投票
1 回答
6765 浏览

parsing - LR(1) - 物品,向前看

我很难理解 LR(1) 中的前瞻原理 - 项目。如何计算前瞻集?

举个例子,我有以下语法:

然后第一个状态将如下所示:

我知道前瞻是什么,但我不知道如何计算它们。我已经用谷歌搜索了答案,但找不到以简单方式解释这一点的网页。

提前致谢