如果文法 L-bLa 1加marker后 2L-NbLa N-E 会怎么样
加上marker后,文法变成:
- L -> bL | aM
- L -> N bL | aM
- N -> E
其中,M表示marker,E表示空串。
这个文法仍然可以生成以a结尾的任意长度的字符串,但是在生成以b结尾的字符串时,必须先加上一个b,然后才能继续生成更多的b。例如,要生成字符串 "bbbab",可以按照如下方式推导:
L => NbL => bNbL => bbNbL => bbbNbL => bbbabM
这里,首先用N推导出一个b,然后用L推导出三个b,最后用aM结束。在这个过程中,marker M的作用是标记字符串的结尾,以便在后续推导中避免生成无效的字符串。
原文地址: https://www.cveoy.top/t/topic/hh3f 著作权归作者所有。请勿转载和采集!