语言的定义

字数

237 字

阅读时间

1 分钟

---

推导和规约

稍微写一点，具体定义和一些其他的没写

• 直接推导：$\alpha \Rightarrow \beta$
  • 就是用产生式的右部替换左部
• 多步推导：${\alpha }_0\Rightarrow {\alpha }_1\Rightarrow {\alpha }_2\Rightarrow ...\Rightarrow {\alpha }_n$
  • 称符号串 ${\alpha }_0$ 经过 n 步推导出 ${\alpha }_n$，可简记为：${\alpha }_0{\Rightarrow }^n{\alpha }_n$
    • 当n = 1时就是直接推导
    • 当n = 0时就是没有推导
    • 直接推导的正闭包：${\Rightarrow }^{+}$ 表示经过正数步推导，即：至少经过一步推导
    • 直接推导的克林闭包：${\Rightarrow }^{\ast }$ 表示经过若干步推导（可以是0步推导）
• 例：
  • 推导过程中忽略单词的复数变化
• 自顶向下的过程：推导
• 自底向上的过程：规约
• 可见：规约是推导的逆过程

贡献者

freeway348

文件历史

最后编辑于 大约 1 个月前查看完整历史

01996-OS