This is the 22nd day of my participation in the Gwen Challenge.More article challenges

Chapter three: Lexical analysis

3.1 Expression of word symbols output by lexical analysis program

(Word type, value of the word itself)

3.2. Normal expressions, normal sets, algebraic laws of obedience

3.3. Normal to normal grammar

3.4. Change from normal grammar to normal form

3.5. Definition of Finite Automata

Can recognize the normal set accurately, that is, recognize the language defined by the normal grammar and the set represented by the normal expression

3.6 deterministic Finite automata (Definition Examination Noun Explanation)


M = ( K . ∑ . f . S . Z ) M=(K,\sum,f,S,Z)

K: Finite set (each element of which is called a state)

∑\sum: finite alphabet (input symbol table)

F: Conversion function

S: S∈KS\in KS∈K is a unique initial state (denoted by =>)

Z: Final state set (represented by a double circle)

Representation: state diagram, matrix

3.7 uncertain Finite Automata (Definition Examination Noun Explanation)

∑ M = (K, f, S, ZK, \ sum, f, S, ZK, ∑, f, S, Z)

K: There are finite sets

∑\sum: a finite alphabet

F: from K ∑ ∗ \ sum ^ * ∑ ∗ to K * all the subsets of the image, namely: K ∗ ∑ ∗ – > 2 kK * \ sum – > 2 ^ ^ * kK ∗ ∑ ∗ – > 2 K, among them 2 k2 ^ k2k said K power set

S: Set of non-empty states (note: there may be multiple uncertain initial states)

Z: final set of states

The difference between:

  • F: The deterministic finite automaton representation is the transformation function; The indeterminate finite automaton represents:From the K.
    ∑ ∗ \sum^ *     Image to the whole subset of K    *
  • S: The deterministic finite automaton has only one initial state; Uncertain finite automata may have multiple initial states

3.8. Transfer ***NFA to DFA

  • Algorithm: subset method

  • steps

    1. First find the initial state, a set of states reachable by nϵ \epsilonϵ, labeled T1

    2. Then mark several sets that T1 can reach through terminals in the terminal set. If they have appeared before, no mark is required. If not, it is marked as a new set T2, T3…

    3. Continue step 2 until all states are marked

    Look at the example

Solve the problem step YYDS

3.9. Simplification of finite automata

purpose

  • Eliminate redundant state
  • Merged equivalent state

Conditions for state equivalence:

  • Rule of consistency: States S and T must be both acceptable and unacceptable
  • The principle of sprawl: States S and T must be converted to equivalent states for all input symbols

Method: segmentation method

3.10. Conversion between normal form and finite automaton

3.11. Formal grammar and finite automata

** Normal formula to minimize DFA solution steps

  1. Turn the NFA
  2. To determine the
  3. To minimize the