Talk:Context-free language
From Wikipedia, the free encyclopedia
 |
This article is within the scope of the WikiProject Philosophy, which collaborates on articles related to philosophy. To participate, you can edit this article or visit the project page for more details. | ||||||||
| ??? | This article has not yet received a rating on the quality scale. | ||||||||
| ??? | This article has not yet received an importance rating on the importance scale. | ||||||||
|
|||||||||
Added homomorphism and inverse homomorphism to the list of closure properties. http://lovelace.spsu.edu/jguzman/OldTerms/CS6413%20051/Downloads/Lectures/Lecture07%20ToC.ppt is a source, but a simple google search for "context free languages" "closed under [inverse] homomorphism" should yield numerous sources.
The beginning is very unclear compared to the Context-free grammar page. The verb "accepted" is particularly confusing. I am not an expert on the subject, but as far as I can tell, "A context-free language is a formal language that is accepted by some pushdown automaton" means, "A formal language is context-free if a pushdown automaton can distinguish between grammatical and ungrammatical sentences."--DCo1 05:36, 2 June 2006 (UTC)
- I must say, the "insufficient context" disclaimer is very ironic :p --Maian 11:45, 29 March 2007 (UTC)
The verb "accepted" refers to the automaton terminating in an accepting state. In formal language theory, an automaton is a finite state control often coupled with a read/write store. Transitions in the state machine are made and the store modified based on the character being read by the machine. A word is accepted by the machine if after all characters of the word are read, the finite state control finishes in an accepting state and the store is in the proper state. The class of automata that accept context free language is a pushdown acceptor.
