Skip to main content

Class_notes_at_17_Oct

上下文无关法及上下文无关语言​

上下文无关法​

w=wRw = w^R 回文语言，记为 LpalL_{pal}，可递归定义为

  • ϵ,0,1\epsilon, 0, 1 均为回文语言
  • 若 ww 是回文，则 0w0 0w0 和 ∣w∣ |w| 也是回文

上下文无关法定义

  • 符号的有穷集（终结符）
  • 变元的有穷集
  • 初始符
  • 产生式（规则）有穷集
    • 变元（头）
    • ⟶\longrightarrow
    • 一个包含零个或多个终结符或变元的串
G=(V,T,P,S)G = (V, T, P, S)

其中 V V 是变元集，TT 是终结符集，PP 是产生式集，SS 是初始符。如 Gpal=({P},{0,1},A,P) G_{pal} = ( \{ P \}, \{ 0, 1 \}, A, P )。

作业​

证明下面两个语言是上下文无关语言。分别构造和生成（验证）他们

  • Lpal={w∈{0,1}∗:w=wR}L_{pal} = \{ w \in \{ 0, 1 \}^\ast : w = w^R \}
  • Le={w∈{0,1}∗:∣w∣0=∣w∣1}L_e = \{ w \in \{ 0, 1 \}^\ast : |w|_0 = |w|_1 \}