4、推导与语言 问题：用文法如何定义一个语言？ 思路：从S出发，反复使用里，对非终结符替换展开， 最后得到全由终结符串组成的一个串 涉及到：巷换->推导>句型->句子->语言
4、推导与语言 问题：用文法如何定义一个语言？ 思路：从S出发，反复使用P，对非终结符替换展开， 最后得到全由终结符串组成的一个串 涉及到：替换->推导->句型->句子->语言
①直接推导：是两个字符串之间的一种关条R 如：(aAβ)R(aYβ)，宅表示： 若A->Y∈P,a、B∈V* 则R就是直接推导，孔记为→ 即：aAβ→aYβ ②推导：如两个串u0、un,存在一个串序列 u0-u1三…→un 则uo孔yun,R记为吉或些 uo吉un:表示从uo出发，经一步或若千步，可推导出un uo类u:表示从uo出发，经0步或若干步，可推导出un
②推导：如两个串u0、un，存在一个串序列 u0 u1 … un 则 u0R1 un，R1记为 或 u0 un：表示从u0出发，经一步或若干步，可推导出un u0 un：表示从u0出发，经0步或若干步，可推导出un ①直接推导：是两个字符串之间的一种关系R 如：（αAβ）R （αγβ），它表示： 若 A->γ∈P，α、β∈V* 则R 就是直接推导，R 记为 即：αAβ αγβ
③怎样由推导引出语言？ √只需在推导中加一些限制 即对： uo去un 或 uo些un ●如令u0为S,即推导要从开始符号开始，那么： S些a,aEV*,称a为G的句型 ●如再要求a∈V-*,则u为G的句子 ●文法G所产生的句子的全体是一个语言，记为L(G) L(G)={a|S吉a&aEV*}
⚫如令u0为S，即推导要从开始符号开始，那么： S α ，α∈V*，称α为G的句型 ⚫如再要求α∈VT *，则α为G的句子 ⚫文法G所产生的句子的全体是一个语言，记为L(G) L(G) = {α|S α & α∈VT* } ③怎样由推导引出语言？ ✓只需在推导中加一些限制 即对： u0 un 或 u0 un
说明 ①由文法G定义语言L是依赖一种运算，关集些 V*中有许多的串，仅有那些5，u)(5,)存在当 关象的u、V才有可能成为语言中的句子。 ②a、B、Y是句型，表示(5，a)(S,B),有 的关条，但宅的构成不全为V的字特。 ③G的句型集，是指存在S古a关系的所有a,该 集的子集是L(G) ④V*一句型集一L(G)
①由文法G定义语言L是依赖一种运算，关系 V*中有许多的串，仅有那些(S,u) (S,v)存在 关系的u、v才有可能成为语言中的句子。 ②α、β、γ是句型，表示(S，α) (S，β) ，有 的关系，但它的构成不全为VT的字符。 ③G的句型集，是指存在S α关系的所有α，该 集的子集是L(G) ④V* 句型集 L(G)
例：GE]: E→E+TT T→TFF F→(E)a 句子：用符号a,十，*，（和）构成的算术表达式
例：G[E]： E→E+T|T T→T*F|F F→(E)|a 句子：用符号a，+， * ，(和)构成的算术表达式