# Convert a dfa to rule for a asterisk case

Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is none terminal symbol:

Statements ::= (Statement ';')*


After converting this rule to NFA, and then do the subset contruction for converting the NFA to DFA, and at last get the dfa:

State0 -> Statement -> State1 -> ';' ->State0
State0 -> ε -> State0


The State0 is the DFA's start state representing the none terminal symbol Statements, also it is the finish state. From State0 input Statement and traslate to State1 and input ';' at State1, translate to State0. Also, State0 could translate to self with the ε.

And after converting the above dfa to regular grammar following the algorithm in dragon book, i get the following grammar rules:

Statements -> ε
Statements -> Statement Extend_NT
Extend_NT  -> ';' Statements


It added the new none terminal symbol Extend_NT, but i want to get the following the regular grammars which does not contain the extend symbol Extend_NT:

Statements -> ε
Statements -> Statement ';' Statements


So the question is that is there any algorithm could get the above result that does not contain the new none terminal symbol Extend_NT?

Or it is just a engineering problem?

Solved: I have solved this by removing the extend symbol in parsing stage. For example, in LALR parsing stage, when to reduce a symbol, i can remove the extend symbol at same time.

• Sorry for confusing you. I have detailed the problem. Nov 17 '21 at 3:42
• Thank you for the clarification. I'm a bit puzzled what is the motivation to translate EBNF -> NFA -> DFA -> regular grammar, but OK.
– D.W.
Nov 17 '21 at 6:07
• You can try to use some pattern-matching-based simplification rule which discovers this exact situation, and performs the required simplification. Nov 17 '21 at 15:38
• @D.W. I am making a parser generator and the input is grammar file in EBNF format. Nov 18 '21 at 1:33