Around Context-Free Grammars -- a Normal Form, a Representation Theorem, and a Regular Approximation
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2015
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916104570404864 |
|---|---|
| author | Cojocaru, Liliana |
| author_facet | Cojocaru, Liliana |
| contents | We introduce a normal form for context-free grammars, called Dyck normal form. This is a syntactical restriction of the Chomsky normal form, in which the two nonterminals occurring on the right-hand side of a rule are paired nonterminals. This pairwise property allows to define a homomorphism from Dyck words to words generated by a grammar in Dyck normal form. We prove that for each context-free language L, there exist an integer K and a homomorphism h such that L=h(D'_K), where D'_K is a subset of the one-sided Dyck language over K letters. Through a transition-like diagram for a context-free grammar in Dyck normal form, we effectively build a regular language R that satisfies the Chomsky-Schutzenberger theorem. Using graphical approaches we refine R such that the Chomsky-Schutzenberger theorem still holds. Based on this readjustment we sketch a transition diagram for a regular grammar that generates a regular superset approximation for the initial context-free language. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1512_09207 |
| institution | arXiv |
| publishDate | 2015 |
| record_format | arxiv |
| spellingShingle | Around Context-Free Grammars -- a Normal Form, a Representation Theorem, and a Regular Approximation Cojocaru, Liliana Formal Languages and Automata Theory 68Q45, 68Q42 F.4.2, F.4.3, G.2.2 We introduce a normal form for context-free grammars, called Dyck normal form. This is a syntactical restriction of the Chomsky normal form, in which the two nonterminals occurring on the right-hand side of a rule are paired nonterminals. This pairwise property allows to define a homomorphism from Dyck words to words generated by a grammar in Dyck normal form. We prove that for each context-free language L, there exist an integer K and a homomorphism h such that L=h(D'_K), where D'_K is a subset of the one-sided Dyck language over K letters. Through a transition-like diagram for a context-free grammar in Dyck normal form, we effectively build a regular language R that satisfies the Chomsky-Schutzenberger theorem. Using graphical approaches we refine R such that the Chomsky-Schutzenberger theorem still holds. Based on this readjustment we sketch a transition diagram for a regular grammar that generates a regular superset approximation for the initial context-free language. |
| title | Around Context-Free Grammars -- a Normal Form, a Representation Theorem, and a Regular Approximation |
| topic | Formal Languages and Automata Theory 68Q45, 68Q42 F.4.2, F.4.3, G.2.2 |
| url | https://arxiv.org/abs/1512.09207 |