FL&A 笔记一

介绍

FL&A ，全称为 Formal Language and Automata ，中文译名为 形式语言与自动机 ，本系列文章源于所学必修课，在整理知识点基础上对经典的解题思路进行归纳总结

概念介绍

• 字母表 (Alphabet)

  形式符号的 非空有限 集合，常用 表示

  eg. 英文小写字母表

• 字符串 or 串 、字 (word)

  定义需要 基于字母表 ，空串使用 表示

  字符串 的长度记为 ，表示字符串中字符的数量

  eg. 设 ，则 等都是串

• 相关运算

  • 连接 (connection)

    设 , 为串，且 ， ，则 与 的连接为
    
    字符串的连接满足 结合律，且有
    

  • 幂运算

    设 为字母表， 为任意自然数，定义

    2. 设 ，则
    3. 中的元素只能有以上两种方式生成

  • *闭包
    

  • +闭包
    

• 语言 (language)

  设 为字母表，则 任何 集合 是字母表 上的一个语言

  • 连接 (concatenation)
    

  • 闭包 (closure)