2015/12/30 by Liliana Cojocaru, Cojocaru, Liliana
Computer Science · #68Q42 #68Q45 #Algorithms and Data Compression #Authorship Attribution and Profiling #F.4.2 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #G.2.2 #Natural Language Processing Techniques #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1512.09207
openalex publication_date 2015/12/30 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
We introduce a normal form for context-free grammars, called Dyck normal\nform. This is a syntactical restriction of the Chomsky normal form, in which\nthe two nonterminals occurring on the right-hand side of a rule are paired\nnonterminals. This pairwise property allows to define a homomorphism from Dyck\nwords to words generated by a grammar in Dyck normal form. We prove that for\neach context-free language L, there exist an integer K and a homomorphism h\nsuch that L=h(D'K), where D'K is a subset of the one-sided Dyck language over\nK letters. Through a transition-like diagram for a context-free grammar in Dyck\nnormal form, we effectively build a regular language R that satisfies the\nChomsky-Schutzenberger theorem. Using graphical approaches we refine R such\nthat the Chomsky-Schutzenberger theorem still holds. Based on this readjustment\nwe sketch a transition diagram for a regular grammar that generates a regular\nsuperset approximation for the initial context-free language.\n