search

xxleyi / learning_list

聚集自己的学习笔记
10 stars 3 forks source link

编译器之 Finite Automata #279

Open xxleyi opened 3 years ago

xxleyi commented 3 years ago

Finite Automata 有限自动机

quote from wiki:

image

The set of strings that M accepts is the language recognized by M and this language is denoted by L(M).

上面介绍的是 DFA，其实还有 NFA： image image image

quote from https://brilliant.org/wiki/regular-languages/ :

Translating between Regular Languages, Finite Automata, and Regular Expressions

Finite automata and regular expressions are different ways to represent regular languages.

Finite automata can be used to generate strings in a regular language. A finite automaton for a particular language is “programmed,” in a way, to generate the strings of a given language through its states and transition functions. You can walk through a finite state machine to see what strings are able to be made and therefore are part of the language the machine described, or you can feed it an input string to see if a given input can be made by the machine.

Note: The symbol epsilon, ϵ, represents transitions on the empty string, sometimes called a "null transition." This means that the machine can take these transitions without needing to read a particular symbol on the input.

A regular expression is one way to represent a regular language as a string. For example, the regular language described by the regular expression 0*1|1*0 means strings that either contain any number of 0’s followed by a single 1 or any number of 1’s followed by a single 0. This regular expression can be represented by the following finite state machine:

The regular expression (01)*11(10)*, which is the language of strings starting with any number of “01” substrings, followed by two 1’s and then any number of “10” substrings, can be represented with the following finite state machine:

image