In a transition diagram, the language L(D) where D is the diagram is defined as all the words that are formed from following an "accepting" walk. Does the same apply for languages of regular grammars too? They are defined by using 4 sets (terminal, non-terminal, initial non-terminal, rules) so there is no such thing as "accepting states" at the definition. The language of a regular grammar are the words that can be produced from that grammar, but do they always end in an "accepting" state?


There is a one-to-one correspondence between NFAs and right regular grammars without productions of the form $A \to a$.

Given a right regular grammar with productions of the form $A \to aB$ and $A \to \epsilon$ and starting symbol $S$, create an NFA in which:

  • The states are all nonterminals.
  • The initial state is $S$.
  • A state $A$ is final if there is a production $A \to \epsilon$.
  • There is an edge labeled $a$ from $A$ to $B$ if there is a production $A \to aB$.

This NFA accepts the same language as the grammar.

You can also easily carry out the transformation in the other direction.

This shows that in the absence of rule of the form $A \to a$, the analogs of accepting states are nonterminals with productions of the form $A \to \epsilon$.

We can replace a production $A \to a$ by a pair $A \to aX$, $X \to \epsilon$, where $X$ is a nonterminal which is common to all such productions, but doesn't appear anywhere else. We can think of $X$ as the accepting sink. A production $A \to a$ signifies a possible transition to the accepting sink.


Your question confuses automata and grammars.

Grammars do not have states.

Grammars generate words by substituting substrings in words to form other words according to the grammar's rules. So instead of ending up in a state you end up with a word.

The all-terminal words (i.e. containing no nonterminals) among those are defined to be the words the grammar generates.

So a word being all-terminal is equivalent to a state being accepting. Another notion of acceptance for grammars would be superfluous.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.