3.写一个上下文无关文法(CFG),使其语言是能被5整除且不以0开头的无符号整数的集合。
时间: 2023-06-11 14:09:56 浏览: 173
无符号整数
以下是一个上下文无关文法(CFG),它描述了一个能被5整除且不以0开头的无符号整数的集合:
S -> A0 | A5
A -> 1A | 2A | 3A | 4A | 5A | 6A | 7A | 8A | 9A | ε
文法中,S是起始符号,A表示数字串。它的含义是,一个数字串可以是以 1-9 中的任何一个数字作为开头,后跟任意个由 1-9 数字组成的数字串,最终以 0 或 5 结尾的数字串。
例如,可以通过该文法生成 15, 20, 305, 999990 等数字。但是,该文法无法生成 0, 5, 10, 25 等数字,因为它们不是以 1-9 中的数字开头。
阅读全文