鉴于语言
L1={anb2m|n,m≥1}
L2={anb3n|n≥0}
L = L1 ∩ L2
我知道这是常规语言，可以用 PDA 来表示。L1L2
但我不明白答案L是什么。这个解决方案是如何计算的？{a2nb6n|n≥1}
问问题
4176 次
1 回答
7
语言只是一组（有效字符串），所以我们在这里实际上只是整数运算中的一个简单问题。只需要去掉形式语言的优雅装束，就能找到问题的本质。
两者都是和的子集；也就是说，它们由一些s 和一些s 组成。限制条件为正偶数，因为它必须是某个整数。限制条件正好是。L1L2{acount(a)bcount(b)|j,k≥0}abL1count(b)2mm≥1L2count(b)3×count(a)
现在，用谓词定义的两个集合的交集是两个谓词都为真的元素集合。socount(b)必须能被 2 和 3 整除，也就是说它必须能被 6 整除；换句话说，它必须是6n某个正整数n。这意味着count(a)一定是2n因为 s 的数量正好是 s 的三倍b。这给了你提供的答案。
Like ,不是常规的，但可以使用非常相似的 PDA 来实现。L2L
于 2017-02-17T15:08:38.373 回答