# Tag Info

43

You are right, there always is a context in some sense. I don't think you can understand what "context" means in "context-free" without understanding a production. A production is a substitution rule. It says that, to generate strings within the language, you can substitute what is on the left for what is on the right: A -> xy This means that the ...

32

It's context-free. Here's the grammar: $S \to A | B|AB|BA$ $A \to a|aAa|aAb|bAb|bAa$ $B \to b|aBa|aBb|bBb|bBa$ $A$ generates words of odd length with $a$ in the center. Same for $B$ and $b$. I'll present a proof that this grammar is correct. Let $L = \{a,b\}^* \setminus \{ww \mid w \in \{a,b\}^*\}$ (the language in the question). Theorem. $L = L(S)$. ...

30

The context can be explained with regards to the production rules allowed for different grammars in Chomsky hierarchy. If you consider context-free grammars, their production rules have the following form: $$A \rightarrow \alpha$$ So, you can observe that the left part of this kind of rules is made up of only one non-terminal symbol; thus, the ...

24

Context-free grammars are allowed to contain unproductive rules. This is accepted, because every CFG generates the same language as some proper CFG which contains no unproductive rules, no empty string productions, and no cycles; so it is safe to assume that a CFG is proper without loss of generality.

21

If $L$ is context-free then there is a PDA $\mathscr{P}$ that accepts it. If $M$ is regular then there is a DFA $\mathscr{F}$ that accepts it. The intersection language consists of the words that are recognized by $\mathscr{P}$ and $\mathscr{F}$. Any word that is in the intersection is accepted by $\mathscr{F}$, but not all words that are accepted by $\... 19 Let us assume$2$CFLs$L_1$and$L_2$and their corresponding grammars be$S_1$and$S_2$respectively. It is very straightforward to see that the union of the two, represented by the new grammar as $$S \to S_1 \mid S_2$$ is also a CFG, as the rule of being context-free is still not violated. Context-free grammar But to prove that they are not closed under ... 17 The language$L_1= \{ww \mid w \in \{a,b\}^*\}$is not context-free (as can be shown using the pumping lemma; see here). Its complement$L_2 = \{a,b\}^* \setminus L_1$is context-free (as shown here). This gives a simple and elegant example of a context-free language (over a binary alphabet) whose complement is not context-free, as you requested. 17 Let$G$be a context free grammar, and let us assume that it is in Chomsky normal form. If it's not, we'll convert it first. An important property of this normal form is that the only way to derive the empty word is with the single rule$S_0\to \epsilon$(where$S_0$is the initial variable, which cannot be derived from other variables). Thus, any other ... 17 Given a derivation tree for a word, you can "implement" it as a sequence of productions in many different ways. The leftmost derivation is the one in which you always expand the leftmost non-terminal. The rightmost derivation is the one in which you always expand the rightmost non-terminal. For example, here are two parse trees borrowed from Wikipedia: The ... 17 "Context" is surrounding text. Context-free grammars are context-free in the sense that the rules look like$A\to\text{things}$, rather than$\text{stuff}\,A\,\text{more-stuff}\to\text{things}$. The left-hand side of a rule is always a single non-terminal symbol. That is, the rules for expanding a non-terminal symbol don't depend on what text appears around ... 16 The language consisting of the words$w_1,w_2,\ldots,w_n$is generated by the context-free grammar $$S \to w_1 \mid w_2 \mid \cdots \mid w_n.$$ 15 The example you see on Wikipedia: put$A=\{a^n b^n c^m\}$,$B=\{a^m b^n c^n\}$. It's easy to see$\overline{A}$and$\overline{B}$are context-free by defining a PDA; you can note that they're deterministic context-free languages, which is a class closed under complement. Therefore$\overline{A} \cup \overline{B}$is a context-free language with a non-... 15 "I know that this statement is false, but couldn't find an example to disprove it." It might come as a surprise to you that, in fact, every non-context-free language can be a counterexample. We have the following fact, assuming any fixed alphabet$\Sigma$. Let$L$be a language. Then there exist regular languages$L_1, L_2,...$such that$L=\cap_{...

14

A practical approach that in many examples works [but not always, I know] is trying to find the nesting structure of the strings in the language. "Nested dependencies" have to be generated at the same time in different parts of the string. Also we have the basic toolbox: concatenation: $S\to S_1S_2$ if you can split the language in two consecutive ...

14

What you have shown is technically not a grammar, only part of it. A grammar is formally defined as the tuple $(N, \Sigma, P, S)$, where: $N$ is a set of non-terminal symbols $\Sigma$ is a set of terminal symbols $P$ is a set of production rules $S$ is a start symbol You have only provided $P$, but to have a grammar, you also need $N$, $\Sigma$ and $S$. $... 14 Affix grammars (parameterised context-free grammars) were studied extensively by the eminent Dutch computer scientist Cornelis HA Koster, starting with his 1962 paper "Basic English, a generative grammar for a part of English", co-written with LGLT Meertens. In 1970, he produced a formalism of the concept; a useful overview is available in his 1971 paper "... 13 A stronger version of the Ogden's condition (OC) is the Bader-Moura’s condition (BMC) A language$L\subseteq \Sigma^*$satisfies BMC if there exists a constant$n$such that if$z \in L$and we label in it "distinguished" positions$d(z)$and$e(z)$"excluded" positions, with$d(z) > n^{e(z)+1}$, then we may write$z = uvwxy$such ... 13 The classical example is$L = \{ a^i b^j c^k : i,j,k \text{ all different} \}$. Wise shows in his paper A strong pumping lemma for context-free languages that neither the Bar-Hillel pumping lemma nor Parikh's theorem (stating that the set of lengths of words in a context-free language is semi-linear) can be used to prove that$L$is not context-free. Other ... 13 The C language has typing rules. For example, you can't divide two pointers, and when you call a procedure accepting a pointer, you can't use a double. A C compiler analyzes its source in several phases: first there is lexical analysis, then the source is parsed, and so on. These phases are abstraction, and in fact additional information is passed from phase ... 13 Context-free grammars cannot express the rules of INDENT/DEDENT and so Python (which we use today in practice with INDENTs/DEDENTs)is not pure CF. Parsers (or lexical analyzers or lexers) for these languages use additional techniques to handle those structures. For example keep track of indentation levels, or tokenizer (scanners) may count number whitespaces ... 12 There are at least two relevant uses. Simplicity of proofs There are plenty of proofs around context-free grammars, including reducability and equivalence to automata. Those are the simpler the more restricted the set of grammars you have to deal with is. Therefore, normal forms can be helpful there. As a concrete example, Greibach normal form is used to ... 12 This characterization of bounded context-free languages is due to Ginsburg ("The Mathematical Theory of Context-Free Languages"), and appears as Corollary 5.3.1 in his book. For general$k$there are some restrictions on the semilinear sets, but for$k \leq 2$these restrictions are always satisfied, and so it is straightforward to deduce that the complement ... 12 The classic consequence of$a^nb^n$being context-free rather than regular is on opening and closing brackets.$a^nb^n$represents the simplest possible case of this: no interleaving of opens and closes and no intervening characters. Regular expressions can't even deal with this most basic case. 12 The Parikh image$\Psi$of a word is a vector counting the number of each of the letters in the alphabet: for example$\Psi( abbabaaca ) = (5,3,1)$assuming the alphabet is$\{a,b,c\}$. The Parikh image of a language is the set of Parikh images of the strings in the language:$\Psi( \{a^nb^nc^n\mid n\ge 0 \}) = \{(n,n,n)\mid n\ge 0 \}$. The theorem states ... 12 Compatibility of left associativity and LL(1) parsing You just hit one of the major inconsistencies in the use of context-free (CF) syntax. People want to choose grammars so that the parse-tree will reflect the intended structure of the sentence, close to its semantics, especially in the case of non associative operators, such as application. This was ... 12 Quoting from Amiram Yehudai, The Decidability of Equivalence for a Family of Linear Grammars, Information and Control 47, 122-136 (1980), page 1: The equivalence problem for various families of languages is of great interest in the theory of formal languages. This problem is decidable for regular languages (Rabin and Scott, 1959) and undecidable for ... 12 You can think of it as " every CFL is Recursive". And Recursive languages are closed under complementation. Therefore, if a language$L$is CFL then it is also recursive and hence,$L^C$is also recursive. 11 There is one characterisation of CFL that can be of use, the Chomsky-Schützenberger theorem. Dyck language Let$T$an alphabet. We define the Dyck-language$D_T \subseteq (T \cup \hat{T})^*$of$T$by the context-free grammar$G = (\{S\}, T \cup \hat{T}, \delta, S)$with$\delta$given by$\qquad\displaystyle S \to aS\hat{a}S \mid \varepsilon, \quad ...

11

$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context-free language according to Pumping lemma for context-free languages. Suppose $L$ is context-free. The pumping lemma says there exists some integer $p \ge 1$ such that every string $s$ in $L$ where $|s| \ge p$ can be written as $s=uvwxy$ where $|vwx|\le p$, $|vx|\ge 1$ and $uv^nwx^ny$ is in $L$ for all $n \... 11 You are confusing two different statements.$\mathrm{CFL} \cap \mathrm{REG} = \mathrm{REG}$or, equivalently, for all$L_1 \in \mathrm{REG}$:$L_1 \in \mathrm{CFL}$. For all$L_1 \in \mathrm{REG}$,$L_2 \in \mathrm{CFL}$:$L_1 \cap L_2 \in \mathrm{CFL}\$. The first makes a statement on two sets of languages (aka language classes), the second makes one ...

Only top voted, non community-wiki answers of a minimum length are eligible