1
$\begingroup$

This question is directed at DFAs/NFAs and regular languages and regular grammars.

Define the "descriptional complexity" of a language as the size complexity of the family of DFAs that recognize L i.e. the number of states of the minimal DFA that recognizes L.

A regular grammar generates a regular language, so I would like to learn whether there's a complexity measure on regular grammars which relates to the size-complexity of the DFAs that recognize a language generated by a regular grammar?

For instance, right-regular grammars convey the computational scheme of an NFA: the non-terminals represent the states of the NFA. Is the number of non-terminals a natural measure to quantify the complexity of a regular grammar?

I would like to highlight that I searched the site (I hope carefully) before asking the question, and I am still lacking an answer. I know there's abundant literature on CFGs and their relevant definitions of complexity, however, this is not what I am asking about.

Any thoughts and answers are appreciated.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.