首页 动态 消费 创业 汽车 商业 房产 互联网 纵横 聚焦 快讯 热点 手机版
资讯 > 房产 >

形式文法定义是什么?形式文法举例都是什么?

来源:创视网 发布时间:2023-05-10 13:40:49

形式文法定义是

形式文法被严格地定义为四元组G=(V,T,P,S),其中V和T分别是变元和终结符的有穷集合,并且V和T没有公共元素,即V∩T=Æ。S是一个特殊变元,称为开始符号。P是生成式的有穷集合,生成式的基本形式是:a→β,这里a和β,这里a和β都是(V∪T)*中的元素,即它们都是由变元和终结符组成的符号串,但要求a至少含有一个非终结符。在形式文法定义中,生成式集合P是至关重要的。在对使用符号的惯例作某些约定后,仅仅考查生成式,就能推断出一个文法的变元、终结符和开始符号,故可以友爱过列出生成式来定义一个形式文法。

形式文法举例

举例来说,假设字母表只包含 'a' 和 'b' 两个字符,初始符号是 'S' ,我们应用下述规则:

1. S -> aSb

2. S -> ba

于是我们可以通过把 "S" 重写为 "aSb"(规则1),我们还可以继续应用这条规则把 "aSb" 重写为 "aaSbb"。这个重写的过程不断重复,直到结果中只包含字母表中的字母为止。在例子中,我们可以得到 S -> aSb -> aaSbb -> aababb 这样的结果。由文法刻画的语言包含了所有可以这样产生的字串,比如 ba, abab, aababb, aaababbb 等等。

责任编辑:FG003


 

网站首页 | 关于我们 | 免责声明 | 联系我们
 

所有文章、评论、信息、数据仅供参考,使用前请核实,风险自负。
 

Copyright 2013-2020  高陵经济网 版权所有 京ICP备2022016840号-34
 

营业执照
 

联系邮箱:920 891 263@qq.com     glxcb.cn    All Rights Reserved