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.


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.