问题标签 [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.
context-free-grammar - L* 和 Σ* 之间的差异
有人可以解释和之间的确切区别Σ*
,语言L*
在哪里,
L
语言Σ
的字母在L
哪里?
谢谢
math - 确保:仅为无限常规语言抽取引理?
所以这不是关于抽水引理及其工作原理,而是关于先决条件。
在网络上你可以读到的任何地方,常规语言都必须通过抽引引理,但是没有人谈论有限语言,它实际上是常规语言的一部分。
所以我们可能都同意,以下语言是一种有限语言,也是一种常规语言,但它绝对没有通过抽水引理:
L = {'abc', 'defghi'}
请告诉我是否根本没有人写它,或者我们为什么错了——甚至没有。
regex - 查找包含子字符串 01a 和字母表 {0,1,a} 中偶数个 1 的字符串的正则表达式
由其描述给出的常规语言:
{0,1, a} 的所有字符串的集合,其中包含子字符串 '01a' 和偶数个 '1'。例如,“01a1”、“101a”、“101a101”。
如何构造一个指定语言的正则表达式?
turing-machines - 有没有什么简单的方法可以解决“构建图灵机……”的问题?
我理解图灵机的逻辑。当给出图灵机时,我可以理解它是如何工作的以及它是如何停止的。但是当它被要求构建一个图灵机时,它就更加困难了。
有什么简单的方法可以找到以下问题的答案:
我想绘制这些图灵机的图表?有没有什么方法,比如填表然后画图等等?
我在网上搜索了很多关于这个主题的内容。只有答案(只有图表)。没有解释它是如何解决的。
提前致谢
c - XML的形式语法
我试图在 C 中为 XML 文件构建小型解析器。我知道,我可以找到一些完成的解决方案,但是,我只需要一些用于嵌入式项目的基本东西。我正在尝试创建用于描述没有属性的 XML 的语法,只有标签,但它似乎不起作用,我无法弄清楚原因。
这是语法:
这是实现此语法的 C 代码的一部分:
}
编辑:这是不满足此语法的 XML 文件示例:
它在输出端给出 END EXPECTED。
finite-automata - 非线性、明确和非确定性 CFL 的示例?
在形式语言的乔姆斯基分类中,我需要一些Non-Linear, Unambiguous and also Non-Deterministic
上下文无关语言(N-CFL)的例子吗?
线性语言:线性语法是可能的(⊆ CFG),例如
L 1 = {a n b n | n≥0}确定性上下文无关语言(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 且明确的示例?
给定下面的维恩图:
也在这里问
email - 电子邮件地址格式的正式定义是什么?
我想知道构建电子邮件地址的正式定义。
我不只是想要答案,而是如何得到它,因为我想自己学习如何去做。
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 那么我得到
这是正确的吗 ?我在“正确的道路”上吗?
谢谢
context-free-grammar - 上下文无关语法 - LR(0) DFA
我需要一些帮助来为上下文无关语法构建 LR(0) DFA。
这就是我所拥有的:
状态
然后我有一个标记a
为:
状态
从这个状态,一个箭头标记a
为:
状态:
这就是我的问题开始的地方。正如你所看到的,我从这个状态得到两个箭头B
,因为我有:
我做错了什么?
parsing - LR(1) - 物品,向前看
我很难理解 LR(1) 中的前瞻原理 - 项目。如何计算前瞻集?
举个例子,我有以下语法:
然后第一个状态将如下所示:
我知道前瞻是什么,但我不知道如何计算它们。我已经用谷歌搜索了答案,但找不到以简单方式解释这一点的网页。
提前致谢