【自然语言处理】NLP入门（九）：1、正则表达式与Python中的实现（9）：自动机：⾮确定有限⾃动机与正则表达式

一、前言

  本文将介绍自动机理论，简介有限自动机(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]$/
1

【自然语言处理】NLP入门（七）：1、正则表达式与Python中的实现（7）：常用正则表达式、re模块：findall、match、search、split、sub、compile

【自然语言处理】NLP入门（八）：1、正则表达式与Python中的实现（8）：正则表达式元字符详解

8、自动机

1. 有限自动机(Finite Automata, FA)

准备阅读天书：

定义

  有限自动机是一种最基本、最简单的自动机模型。它由 一个有限的状态集合、一个有限的输入符号集合、状态转移函数、初始状态和终止状态集合组成。

确定性和非确定性

• 确定性有限自动机(DFA) 在每个状态下对给定的输入符号只有一个确定的转移路径。即对于任意$q\in Q$和$a\in \Sigma$,都有$\delta (q,a)$是一个单一状态。

  • 一个确定的有限自动机(DFA)可以用五元组表示为: $DFA=(Q,\Sigma ,\delta ,q_0,F)$，其中:
    • $Q$ 是一个有限状态集合
    • $\Sigma$ 是一个有限输入符号集合
    • $\delta :Q\times \Sigma \to Q$ 是状态转移函数
    • $q_0\in Q$ 是唯一的初始状态
    • $F\subseteq Q$ 是一个终止状态集合

• 非确定性有限自动机(NFA) 则允许在某个状态下对于同一输入符号有多个转移路径,需要并行 模拟所有可能路径。它的转移函数映射到一个状态集合,即 $\delta :Q\times \Sigma \to \mathcal{P}(Q)$,其中$\mathcal{P}(Q)$是$Q$的幂集。此外,NFA可以有一个初始状态集合,而不是单个初始状态。

  • 一个NFA可以表示为五元组: $NFA=(Q,\Sigma ,\delta ,I,F)$其中
    • $I\subseteq Q$是初始状态集合

应用

• 编译器词法分析:用于识别和验证程序中的单词符号。
• 正则表达式识别:有限自动机是实现正则表达式匹配的理论基础。
• 电路设计: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. 典例

  给定列表$x=[“13915556234”,“13025621456”,“15325645124”,“15202362459”]$，检查列表中的元素是否为移动手机号码，这里移动手机号码的规则是:手机号码共11位数字;以13开头，后面跟4、5、6、7、8、9中的某一个;或者以15开头，后面跟0、1、2、8、9中的某一个。

正则表达式

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} 不是移动手机号码")
1
2
3
4
5
6
7
8
9

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} 不是移动手机号码")
1
2
3
4
5
6
7
8
9
10

自动机

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} 不是移动手机号码")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24