Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Solutions of equations in languages
Hesselink W. Formal Aspects of Computing22 (5):537-545,2010.Type:Article
Date Reviewed: Feb 10 2011

Context-free grammars, their implications, and their uses have been understood and well studied for more than a half-century, but the author demonstrates that there is more to learn and to make explicit by articulating two characteristics of grammars and equations, one new and one old but forgotten, and by presenting a new proof of a familiar characteristic of context-free grammars.

After a concise introduction that deftly summarizes what is to follow, the paper proves an unsurprising but unpublished finding: a solution to a system of equations that corresponds to a grammar is the smallest such solution if it meets a specific criterion. The paper also proves the little-noted finding that if a grammar has more than one solution, it has a nonempty unguarded set. These two results then drive a method for determining the grammar of a language and a proof of the well-known finding that if a language is accepted by a pushdown automaton, it is context free.

Readers interested in grammars and the formal aspects of computer science will find this paper of interest, and writers in these areas will encounter a tightly organized argument that can serve as a model of exposition.

Reviewer:  Marlin Thomas Review #: CR138776 (1107-0748)
Bookmark and Share
  Featured Reviewer  
 
Formal Languages (F.4.3 )
 
 
Automata (F.1.1 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Formal Languages": Date
The three subfamilies of rational &ohgr;-languages closed under &ohgr;-transduction
Timmerman E. Theoretical Computer Science 76(2-3): 243-250, 2001. Type: Article
Jul 1 1992
Introduction to formal languages
Révész G., Dover Publications, Inc., New York, NY, 1991. Type: Book (9780486666976)
Jan 1 1993
Fibonacci morphisms and Sturmian words
Séébold P. Theoretical Computer Science 88(2): 365-384, 1991. Type: Article
Oct 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy