嵌入式系统与单片机|技术阅读
登录|注册

您现在的位置是：嵌入式系统与单片机 > 资源下载 > 数据结构 > 上下文无关文法（Context-Free Grammar, CFG）是一个4元组G=(V, T, S, P)

上下文无关文法（Context-Free Grammar, CFG）是一个4元组G=(V, T, S, P)

  • 资源大小：302 K
  • 上传时间： 2024-04-19
  • 上传用户：jybgyf
  • 资源积分：2 下载积分
  • 标      签： Context-Free Grammar CFG

资 源 简 介

上下文无关文法（Context-Free Grammar, CFG）是一个4元组G=(V, T, S, P)，其中，V和T是不相交的有限集，S∈V，P是一组有限的产生式规则集，形如A→α，其中A∈V，且α∈(V∪T)*。V的元素称为非终结符，T的元素称为终结符，S是一个特殊的非终结符，称为文法开始符。 设G=(V, T, S, P)是一个CFG，则G产生的语言是所有可由G产生的字符串组成的集合，即L(G)={x∈T* | Sx}。一个语言L是上下文无关语言（Context-Free Language, CFL），当且仅当存在一个CFG G，使得L=L(G)。 *⇒ 例如，设文法G：S→AB A→aA|a B→bB|b 则L(G)={a^nb^m | n,m>=1} 其中非终结符都是大写字母，开始符都是S，终结符都是小写字母。

相 关 资 源