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

Qomolangma

发布于 2024-07-30 12:39:51

930

发布于 2024-07-30 12:39:51

一、前言

本文将介绍自动机理论，简介有限自动机(Finite Automata, FA)、下推自动机(Push-down Automata, PDA)、线性有界自动机(Linear Bounded Automata, LBA)、图灵机(Turing Machine, TM)；重点介绍⾮确定有限⾃动机与正则表达式的对应关系。

二、正则表达式与Python中的实现

1、字符串构造

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) 在每个状态下对给定的输入符号只有一个确定的转移路径。即对于任意

q \in Q

和

a \in \Sigma

,都有

\delta(q, a)

是一个单一状态。

- 一个确定的有限自动机(DFA)可以用五元组表示为:

DFA = (Q, \Sigma, \delta, q_0, F)

，其中:

是一个有限状态集合

\Sigma

是一个有限输入符号集合

\delta: Q \times \Sigma \rightarrow Q

是状态转移函数

q_0 \in Q

是唯一的初始状态

F \subseteq Q

是一个终止状态集合

非确定性有限自动机(NFA) 则允许在某个状态下对于同一输入符号有多个转移路径,需要并行 模拟所有可能路径。它的转移函数映射到一个状态集合,即

\delta: Q \times \Sigma \rightarrow \mathcal{P}(Q)

,其中

\mathcal{P}(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} 不是移动手机号码")

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} 不是移动手机号码")

自动机

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} 不是移动手机号码")