当前位置:网站首页>II Transforming regular expressions into finite state automata: NFA state machine recognizes input strings
II Transforming regular expressions into finite state automata: NFA state machine recognizes input strings
2022-06-12 09:20:00 【symop】
original text :https://study.163.com/course/courseMain.htm?courseId=1002830012
Given a regular expression :D*.D | D.D*
Use the program we developed in the previous sections , Build the corresponding... For the above regular expression NFA State machine , The constructed state machine is as follows ( Show the original ):
We will use the above NFA To identify the string 1.2.
In the diagram above , Last state 18, Because there is no way out , therefore , state 18 Is the receiving status .
We go from state to state 17 Start , Remember we said before , Corresponding to ε edge , The state machine can enter automatically without any input characters ε The next state the edge points to . thus , From the State 17, At the same time, we can enter the State :3, 1, 4, 9, 5. A collection of these states , To be exact , Corresponding to a given set of initial states , Through their ε A collection of states that an edge can achieve , We call it ε Closure , Remember to do ε-Closure. Because according to the initial state 17, adopt ε edge , The states we can reach are 3,1,4,9, therefore :
ε-Closure({17}) = { 5,9,17,1,3,4 }
Attention, everyone ,ε In closure collection , Contains the given initial state , Because for any state , It can reach itself without entering any characters , therefore , We default to , Every point implies a path from oneself to oneself ε edge , So it's calculating ε Closure time , The result must include the input state set when calculating the closure , That's why the right side of the above equation contains States 17.
From the input , Read in character 1 after , Get the jump status from ε Find... In the closure collection , From the picture we find , Can read characters 1 The state of , Is the state in the closure set 1,9. From the State 1 Read in character 1 After entering the State 2, From the State 9 Read character 1 After entering the State 10, state 2 and 10 We call it a set of transition states , Write it down as :
move({5,9,17,1,3,4}, ‘1’) = {2, 10}
Next , We are in a state of 2,10 Conduct ε Closure operations , That is to see ,2,10 adopt ε What states can an edge reach :
ε-Closure({2, 10}) = { 10,5,2,11,1,4 }.
The next character we read in is . , Look at the transition set after the input point from the closure set above , According to the state diagram , We learned that , state 5 Input . After entering the State 6, state 11 Receive character . After entering the State 12, So we have :
move({ 10,5,2,11,1,4 }, ‘.’)= { 6,12 }
then , We do this for the transfer set ε Closure operation has :
ε-Closure( 6,12 ) = { 6,12,7,18,16,13,15 }
Attention, everyone , At this point, the closure set contains the receive status 18, It also means that , A string of currently entered characters 1. It can be accepted by our state machine . But because the input has not been processed , So we continue to input unprocessed characters into the state machine , The current character to be entered is 2, therefore :
move({ 6,12,7,18,16,13,15 }, ‘2’)= { 14,8 }
To transfer sets {14,8} Doing closure operations has :
ε-Closure( 14,8 ) = { 14,8,18,16,13 }
here , The closure collection contains the acceptance status 18.
here , All characters have been processed , At the same time, the state machine enters the accept state , So strings 1.2 Can be our NFA Accepted by the state machine .
边栏推荐
- What are the design principles of an automated test framework? I'll sum it up for you. Come and see
- 2024. 考试的最大困扰度-滑动窗口
- L1-019 who goes first
- 剑指 Offer II 016. 不含重复字符的最长子字符串-滑动窗口
- Distributed task scheduling
- Tool classes for extracting zip files
- Common technical questions in functional test interview. Would you like to summarize them?
- How should the test plan be written? A thought teaches you
- JVM garbage collection
- Leetcode 336 palindrome pair (palindrome string + hash)
猜你喜欢

ThreadLocal
数据库常见面试题都给你准备好了
Database common interview questions are ready for you

node示例后台搭建
![Offer:[day 8 dynamic planning (simple)] --- > maximum profit of stock](/img/42/000a3e601ba1771a1ee07fcd800307.jpg)
Offer:[day 8 dynamic planning (simple)] --- > maximum profit of stock

Machine learning notes - circular neural network memo list

Swagger documentation details
Financial test interview questions to help you get the offer

Flink passes in custom parameters or profiles

Description of string
随机推荐
Chapter 3 registers (memory access)
Description of string
Permutation (greedy strategy)
consul 配置相关
Common technical questions in functional test interview. Would you like to summarize them?
最少换乘次数
(13) Text rendering text
Latex common symbols summary
Sword finger offer II 016 Longest substring without repeating characters - sliding window
Complete knapsack problem 1
ADB命令集锦,一起来学吧
帮助你拿到offer的金融测试面试题
功能测试面试常见的技术问题,总结好了你不看?
Basic SQL syntax i
Cas d'essai et spécification de description des bogues référence
MySQL index
测试用例和bug描述规范参考
Mysql database ignores case
网络层IP协议 ARP&ICMP&IGMP NAT
MySQL - Import / export operation