# Tag Info

41

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 ...

30

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.

23

Regular expressions, regular grammars and finite automata are simply three different formalisms for the same thing. There are algorithms to convert from any of them to any other. The basic reason that we have all three is that they were created independently, with the first set of equivalences (there are several other formalisms as well) proven by Kleene (...

22

Grammars are inherently recursive objects, so the answer seems obvious: by induction. That said, the specifics are often tricky to get right. In the sequel I will describe a technique that allows to reduce many a grammar-correctness proof to mechanical steps, provided some creative preprocessing is done. $\newcommand{\lang}{\mathcal{L}(#1)} \newcommand{\... 22 A grammar has "Production rules:" rules about the new sequences of symbols that you can produce from old sequences. In the cases of context-free grammars, this the old sequence is always a single non-terminal symbol. Sometimes people abbreviate "production rules" to "productions". Sometimes people abbreviate "production rules" to "rules". The two are not ... 20 A grammar (not a language!) is ambiguous if there is a word with two "essentially different" parses. Roman numerals are unambiguous - given a roman numeral, it has an unambiguous numerical value. The fact that this correspondence is not one-to-one is beside the point. 20 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$\...

20

It's common to write DFAs which don't have transitions on every symbol. These are called "incomplete" DFAs, and there is really nothing wrong with them as long as it is understood that they are incomplete. But they don't satisfy all of the requirements of algorithms which require complete DFAs, and the complement algorithm you are using is one of those. (...

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 ...

15

Left recursive grammars are not necessarily a bad thing. These grammars are easily parsed using a stack to keep track of the already parsed phrases, as it is the case in LR parser. Recall that a left recursive rule of a CF grammar $G = (V,\Sigma,R,S)$ is of the form: $\alpha \rightarrow \alpha \beta$ with $\alpha$ an element of $V$ and $\beta$ an element ...

15

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 ...

15

As quicksort notes in his comment, languages are infinite objects and it is not possible to feed them to Turing Machines. So we must be content to consider classes of languages for which there eists a finite description. We can for instance consider the context-free languages and give as input the grammar for the language. Unfortunately, even for context-...

14

My favourite example of a context-sensitive language (CSL) is SAT. The Landweber-Kuroda Theorem says that CSL = NSPACE$[n]$. Any SAT instance has a linear-size certificate, so SAT is a CSL. See my question Context-sensitive grammar for SAT? for references and discussion. Many other NP-hard languages are also in CSL by the same reason, such as CLIQUE. ...

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

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 ...

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 Let's have a look at your grammar:$\qquad \begin{align} X &\to aE \mid IXE \mid (X)E \\ E &\to IE \mid BXE \mid \varepsilon \\ I &\to \text{++} \mid \text{--} \\ B &\to \text{+} \mid \text{-} \mid \varepsilon \end{align}$Note that$X$does not need left-factoring: all rules have disjoint FIRST sets¹. If you want to make this obvious, you ... 13 Consider this rule: example : 'a' | example 'b' ; Now consider a LL parser trying to match a non-matching string like 'b' to this rule. Since 'a' doesn't match, it'll try to match example 'b'. But in order to do so, it has to match example...which is what it was trying to do in the first place. It could get stuck trying forever to see whether it can ... 13 No, you can not. Proof by Pumping Lemma: Assume$L$is regular and$n$be the pumping length consider the word$w=0^n10^n$. Thus there are$x,y,z \in \{0,1\}^*$with$|xy|<n$and$|y| > 0$such$xyz=w$. Then$\forall i\in \mathbb{N}_0: xy^iz \in L$. But due to its length constraint$x$and$y$consist of$0$only and all are before the$1$. Thus$xy^...

12

The question is wrong. The second language is also inherently ambiguous. The usual way this is proved is as follows. Suppose $L_2$ had an unambiguous grammar. Let $p$ be the constant promised by Ogden's lemma, and consider the word $a^{p!+p} b^p c^p$. Mark the positions of $b^p c^p$ and apply Ogden's lemma to pump this word to the word $a^{p!+p} b^{p!+p} c^{... 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 Every nonempty context-free language has an ambiguous grammar. Consider any context-free grammar for the language with starting symbol$S$. We add new non-terminals$S',A',B'$, make$S'the new starting symbol, and add the following rules: \begin{align*} &S' \to A' \\ &S' \to B' \\ &A' \to S \\ &B' \to S \end{align*} 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 This falls within the general topic of "grammar induction"; searching on that phrase will turn up tons of literature. See, e.g., Inducing a context free grammar, https://en.wikipedia.org/wiki/Grammar_induction, https://cstheory.stackexchange.com/q/27347/5038. For regular languages (rather than context-free ones), see also Is regex golf NP-Complete?, ... 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 The following grammar is unambiguous yet generates a non-regular language: $$S \to aSb \mid \epsilon$$ 11LL(k)$and$LR(k)$grammars are nice not just because they can be parsed efficiently, but also because we can check if a grammar is$LL(k)$or$LR(k)\$, and because we can generate tables for them (parse tables are used to parse input strings). Note that for these two classes, having the parse table immediately allows you to check whether the grammars are in ...

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