一、前言
本文将介绍自动机理论，简介有限自动机(Finite Automata, FA)、下推自动机(Push-down Automata, PDA)、线性有界自动机(Linear Bounded Automata, LBA)、图灵机(Turing Machine, TM)；重点介绍⾮确定有限⾃动机与正则表达式的对应关系。
二、正则表达式与Python中的实现
1、字符串构造
2、字符串截取
【自然语言处理】NLP入门（一）：1、正则表达式与Python中的实现（1）：字符串构造、字符串截取
3、字符串格式化输出
【自然语言处理】NLP入门（二）：1、正则表达式与Python中的实现（2）：字符串格式化输出(%、format()、f-string)
4、字符转义符
【自然语言处理】NLP入门（三）：1、正则表达式与Python中的实现（3）：字符转义符
5、字符串常用函数
在Python中有很多内置函数可以对字符串进行操作。如len()、ord()、chr()、max()、min()、bin()、oct()、hex()等。
自然语言处理】NLP入门（四）：1、正则表达式与Python中的实现（4）：字符串常用函数
6、字符串常用方法
由于字符串属于不可变序列类型，常用方法中涉及到返回字符串的都是新字符串，原有字符串对象不变
【自然语言处理】NLP入门（五）：1、正则表达式与Python中的实现（5）：字符串常用方法：对齐方式、大小写转换详解
【自然语言处理】NLP入门（六）：1、正则表达式与Python中的实现（6）：字符串常用方法：find()、rfind()、index()、rindex()、count()、replace()
7、正则表达式
正则表达式是一个特殊的字符序列，利用事先定义好的一些特定字符以及它们的组合组成一个“规则”，检查一个字符串是否与这种规则匹配来实现对字符的过滤或匹配。
- Python中，re模块提供了正则表达式操作所需要的功能。
- 元字符是一些在正则表达式中有特殊用途、不代表它本身字符意义的一组字符。
/^1[34578][0-9]$/【自然语言处理】NLP入门（七）：1、正则表达式与Python中的实现（7）：常用正则表达式、re模块：findall、match、search、split、sub、compile
【自然语言处理】NLP入门（八）：1、正则表达式与Python中的实现（8）：正则表达式元字符详解
8、自动机
1. 有限自动机(Finite Automata, FA)
准备阅读天书：
定义
有限自动机是一种最基本、最简单的自动机模型。它由 一个有限的状态集合、一个有限的输入符号集合、状态转移函数、初始状态和终止状态集合组成。
确定性和非确定性
- 确定性有限自动机(DFA) 在每个状态下对给定的输入符号只有一个确定的转移路径。即对于任意
和
,都有
是一个单一状态。
代码语言：txt复制- 一个确定的有限自动机(DFA)可以用五元组表示为: ，其中:
代码语言：txt复制 - 是一个有限状态集合
代码语言：txt复制 - 是一个有限输入符号集合
代码语言：txt复制 - 是状态转移函数
代码语言：txt复制 - 是唯一的初始状态
代码语言：txt复制 - 是一个终止状态集合
- 非确定性有限自动机(NFA) 则允许在某个状态下对于同一输入符号有多个转移路径,需要并行 模拟所有可能路径。它的转移函数映射到一个状态集合,即
,其中
是
的幂集。此外,NFA可以有一个初始状态集合,而不是单个初始状态。
代码语言：txt复制- 一个NFA可以表示为五元组: 其中
代码语言：txt复制 - 是初始状态集合
应用
- 编译器词法分析:用于识别和验证程序中的单词符号。
- 正则表达式识别:有限自动机是实现正则表达式匹配的理论基础。
- 电路设计:Mealy和Moore机器可用于设计组合逻辑和时序逻辑电路。
- 文本处理:文本编辑器、拼写检查器等都可以使用有限自动机来识别模式。
- 机器学习和人工智能中的模型:可以用作学习和决策的简单模型。
2. 下推自动机(Push-down Automata, PDA)
定义
下推自动机是一种带有堆栈存储的扩展有限自动机模型。它可以通过推入和弹出堆栈中的元素来记录和追踪更多信息。
- 确定性下推自动机(DPDA)在每个状态和输入符号对应堆栈顶端符号时,只有一个确定的动作。
- 非确定性下推自动机(NPDA)在某些情况下可能有多个可选动作。
应用
- 编译器语法分析:用于识别和验证程序语法结构,是编译器前端的关键部分。
- 表达式求值:可以高效地对包括嵌套在内的各种表达式进行求值。
- 软件工程中的模型验证:用于验证软件模型的正确性。
- 网络协议解析和验证:确保网络消息遵循正确的语法和格式规范。
- 密码学中的加密解密算法:实现一些基于上下文的加密解密算法。
- 模式匹配和自然语言处理:用于分析句子结构、词性标注和语法树构建。
3. 线性有界自动机(Linear Bounded Automata, LBA)
定义
线性有界自动机是一种受存储空间限制的非确定性图灵机变体。它的存储空间受输入长度的线性约束,但在这个限制内可以按照任意方式移动读写头。LBA可以识别和接受所有的上下文有关语言。
应用
- 遗传编程:LBA可以用作遗传编程中的理论模型。
- 识别上下文相关语言:线性有界自动机的主要应用领域。
- 博弈论建模和分析:可用于对代理之间的交互进行建模和分析。
4. 图灵机(Turing Machine, TM)
定义
图灵机是一种理论计算模型,由一个无限长度的磁带、一个读写头和一个有限状态控制器组成。根据当前状态和磁带上的符号,它可以执行写入、移动读写头以及改变内部状态等操作。
图灵机被认为是最通用的计算模型,所有可计算的函数理论上都可以由某个图灵机来计算。这一性质被称为"图灵完备"。
应用
- 复杂度理论分析:图灵机的计算能力:是研究算法时间和空间复杂性的理论模型。
- 人工智能、神经网络、机器学习:作为学习和决策过程的抽象模型。
- 生物计算建模:可用于模拟和研究生物系统中的计算过程。
- 数字电路模拟与验证:用于对数字电路进行行为建模和验证。
- 人机交互建模:对人与计算机之间的交互进行理论建模和分析。
5. ⾮确定有限⾃动机与正则表达式的对应关系
- 正则表达式:
ab
- 正则表达式:
a|b
- 正则表达式:
a*
- 例题
6. 典例
给定列表
，检查列表中的元素是否为移动手机号码，这里移动手机号码的规则是:手机号码共11位数字;以13开头，后面跟4、5、6、7、8、9中的某一个;或者以15开头，后面跟0、1、2、8、9中的某一个。
正则表达式
代码语言：javascript复制import re
pattern = r'^(13[4-9]d{8}|15[01289]d{8})$'
x = ["13915556234", "13025621456", "15325645124", "15202362459"]
for phone in x:
if re.match(pattern, phone):
print(f"{phone} 是移动手机号码")
else:
print(f"{phone} 不是移动手机号码")import re
pattern = r'(13[4-9]d{8}|15[01289]d{8})'
x = ["13915556234", "13025621456", "15325645124", "15202362459"]
for phone in x:
if re.findall(pattern, phone):
print(f"{phone} 是移动手机号码")
else:
print(f"{phone} 不是移动手机号码")
自动机
代码语言：javascript复制def is_mobile_phone(phone):
transitions = {
'q0': lambda c: 'q1' if c == '1' else 'q5',
'q1': lambda c: 'q2' if c == '3' else ('q3' if c == '5' else 'q5'),
'q2': lambda c: 'q6' if '4' <= c <= '9' and len(phone) == 11 and phone[-8:].isdigit() else 'q5',
'q3': lambda c: 'q7' if c in '01289' and len(phone) == 11 and phone[-8:].isdigit() else 'q5',
'q5': lambda c: 'q5',
'q6': lambda c: 'q6',
'q7': lambda c: 'q7'
}
state = 'q0'
for char in phone:
state = transitions[state](char)
return state in ('q6', 'q7')
x = ["13915556234", "13025621456", "15325645124", "15202362459"]
for phone in x:
if is_mobile_phone(phone):
print(f"{phone} 是移动手机号码")
else:
print(f"{phone} 不是移动手机号码")
