Talk:Context-free language

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.

Language or grammar?

I believe that here:

The following problems are decidable for arbitrary context-free languages:

• is $L(A)=\emptyset$ ?
• is $L(A)$ finite?..

instead of languages should be grammars. Am I right? -- Obradović Goran (ta^lk 00:13, 10 September 2009 (UTC)

Right now, I'm not completely happy with the way the corresponding section of this article is phrased, but it's more or less correct.

If you want to write a program about the properties of languages, the program must read a finite description of the language and then decide whether the described language has the given property. And as this description must be finite, it is usually an automaton that accepts the given language, or a grammar that generates it.

In other words, the decision problems "Given a context-free language L, is it infinite?" and "Given a context-free grammar G, does it generate an infinite language?" are one and the same. E.g., it is correct to state: "Emptiness of context-free languages is decidable."

Misof (talk) 00:02, 18 December 2009 (UTC)

Context-freeness of $A=\{a^{n}b^{n}c^{m}\mid m,n\geq 0\}$ and $B=\{a^{m}b^{n}c^{n}\mid m,n\geq 0\}$

The statement that these languages are context-free is marked with “citation needed”; what kind of citation is needed? Would a simple demonstration be sufficient?

Here is the grammar for A: S → Sc | aTb | ε; T → aTb | ε. The grammar for B is analogous. Yuri Khan (talk) 14:24, 27 November 2013 (UTC)

I went ahead and tried to incorporate your suggestion into the article. Please improve anything if you like. In this case, I think a demonstration is even better than providing a textbook reference. It is not the kind of fact where you will start a debate, so it will be more convenient for most readers to have a demonstration right at hand. For readers familiar with the topic, this may be a simple exercise. But for those who read the article in order to understand what a context-free grammar is in the first place, it may not be immediate how to construct those grammars. Hermel (talk) 23:08, 28 November 2013 (UTC)

What is even the point of such articles?

Why write them, if you absolutely made sure that nobody in the universe can gain even a single bit of information from them? Everyone who can comprehend them, already is such a expert that he doesn’t need the article. There is literally nobody left that this article would be for.

Frankly, it should be deleted. Or brought into a form that makes it useful. For those who do not know the subject.

— 109.42.178.250 (talk) 21:17, 5 February 2024 (UTC)