用常规语言创建语法 [英] Creating a grammar out of a regular language

问题描述

我在解决这种特殊语言的语法时遇到一些问题，希望您能提供帮助:语言是:Σ= {x，y，z}A = {w |w∈Σ^ ∗∧| w | _x mod 2> = | w | _y mod 2}

I have some problems to figure out a grammar for this special language, hope you could help: The language is: Σ={x,y,z} A = { w | w ∈ Σ^∗ ∧ |w|_x mod 2 >= |w|_y mod 2 }

因为这是如此困难，所以我首先尝试将所有属性放在一个语法中，所以| w | _x mod 2> = | w | _y mod 2和w∈Σ^ ∗，但是没有得到像cacbcacb这样的所有组合等等

Because this one is so hard i tried first to put all properties together in one grammar, so |w|_x mod 2 >= |w|_y mod 2 and w ∈ Σ^∗ , but without getting all combination like cacbcacb etc

我得到的是这样的:ccccc ... caa ... abcbbbcc，然后我用ac-> ca等可更改组合并获得我想要的每个单词.

What I get is something like: ccccc...caa...abcbbbcc and than i use ac -> ca etc to change the combination and to get every word I want.

但是我们也可以做一些上下文无关的语法吗?

But could we do some context free grammar too?

我的爱慕

S → G | U | c | cS | ɛ
G → AGB | ɛ | cG
A → ɛ | a | cA
B → ɛ | bb | cB
U → ab | DaUbE | cU
D → a
E → b
ab → ba
ba → ab
ac → ca
ca → ac
bc → cb
cb → bc

非常不友善.

推荐答案

正如您所说，该语言是常规语言，因此显然不需要上下文相关的语法.

As you say, this language is regular, so there is clearly no need for a context-sensitive grammar.

构造正则表达式是乏味的，对于查找无上下文语法的任务不是特别有用.直接从状态机进行操作更容易，尤其是在这种情况下，因为只有四个状态.

Constructing a regular expression is tedious and not particularly useful for the task of finding a context-free grammar. It's easier to work directly from the state machine, particularly so in this case because there are only four states.

将状态机转换为CFG几乎是微不足道的.每个状态都变成一个非终止状态，您可以从状态转换中读取结果.如果状态 P 转换为符号 a 上的状态 Q ，则CFG的产量为 Q->.P a .然后，起始符号将具有每个最终状态的单位产量.就是这样.

Converting a state machine into a CFG is almost trivial. Each state becomes a non-terminal, and you can read the productions off the state transitions. If state P has a transition to state Q on symbol a, the CFG has the production Q -> P a. The start symbol then has a unit production to each final state. And that's it.

这篇关于用常规语言创建语法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！