Showing cs.FLShow all
2 papers · 1 filter
cs.FL2021
Nonterminal complexity of some families of infinite regular languages
Dmitry Golubenko
Nonterminal complexity of a context-free language is the smallest possible number of nonterminals in its generating grammar. While in general case nonterminal complexity computatio…
cs.FL2017
Proving Parikh's theorem using Chomsky-Schutzenberger theorem
Dmitry Golubenko
Parikh theorem was originally stated and proved by Rohkit Parikh in MIT research report in 1961. Many different proofs of this classical theorems were produced then; our goal is to…