Intereting Posts

Prove that matrix is symmetric and positive definite given the fact that $A+iB$ is.
If f is n-times differentiable, and $f^n$ is never 0, then f has at most n zeros in R
Does existential elimination affect whether you can do a universal introduction?
Sigma notation only for odd iterations
Integral of products of cosines
$\epsilon$-$\delta$ proof, $\lim\limits_{x \to a}$ $\frac{1}{x}$ = $\frac{1}{a}.$
How to compute the determinant of a tridiagonal matrix with constant diagonals?
Question about the cardinality of a space
Condition on a point on axis of the parabola so that $3$ distinct normals can be drawn from it to the parabola.
Singular Distribution
The graph of xy = 1 is connected or not
Does $\lfloor(4+\sqrt{11})^{n}\rfloor \pmod {100}$ repeat every $20$ cycles of $n$?
Open $\sigma$-compact sets with finite measure
$\lim_{n \to \infty} \mid a_n + 3(\frac{n-2}{n})^n \mid^{\frac1n} = \frac35$. Then find $\lim_{n \to \infty} a_n$.
Where did the negative answer come from?

What makes a context free grammar ambiguous?

- Density of halting Turing machines
- Context free languages closure property $\{a^n b^n : n\geq 0\} \cup \{a^n b^{2n}: n\geq 0\}$
- Texture mapping from a camera image (knowing the camera pose)
- How would I find a minimum weight spanning tree for W?
- Induction to prove $2n + 3 < 2^n$
- What math should a computer scientist take in college?
- Floating point arithmetic
- Constructing a NFA for the following language
- Why isn't this a regular language?
- Find the Theta class for the recursion $T(n) = T(3n/4) + T(n/6) + 5n$

A grammar is *ambiguous* if there’s a word which has two different derivation trees. You’ll have to look up *derivation tree* in your textbook since drawing them is awkward, but the idea that it doesn’t matter in which order you’re doing the derivations as long as it’s basically the same derivation.

For example, consider the grammar

\begin{align}

S &\rightarrow AS|a \\

A &\rightarrow a

\end{align}

Let’s derive $aa$ twice: $$ S \rightarrow AS \rightarrow Aa \rightarrow aa $$ $$ S \rightarrow AS \rightarrow aS \rightarrow aa $$ These derivations share the same derivation tree:

However, consider now the grammar

\begin{align}

S\rightarrow SS|a

\end{align}

generating the same language.

There are now two “really” different derivations for $aaa$: $$S \rightarrow SS \rightarrow Sa \rightarrow SSa \rightarrow Saa \rightarrow aaa$$ $$S \rightarrow SS \rightarrow aS \rightarrow aSS \rightarrow aaS \rightarrow aaa$$

In the first derivation, the first two $a$’s are derived together, whereas in the second derivation, it is the second two $a$’s which are derived together. So it’s $(aa)a$ vs. $a(aa)$.

In this case, the language $a^+$ has an unambiguous grammar (the first one I exhibited), but in other cases, all grammars are ambiguous; such languages are called *inherently ambiguous*. See my other answer for more on that.

Intuitively, what makes a language inherently ambiguous is that it is composed of distinct parts which have some intersection; the intersection cannot be “singled out”, and therefore the only way to approach is is through the distinct parts.

For example, the language of words of the form $a^xb^yc^z$, where $x=y$ or $y=z$, is context-free, since it’s the union of $a^nb^nc^*$ and $a^*b^nc^n$. However, words of the form $a^nb^nc^n$ cannot be “singled out” since that language is not context-free, so we would expect the language to be inherently ambiguous.

The formal proof (using Ogden’s lemma) goes like this. Consider the word $a^nb^nc^{n!}$, where $n$ is “big enough”. By Ogden’s lemma, the $a^nb^n$ can be pumped up, and so we can derive $a^{n!}b^{n!}c^{n!}$. Similarly, we can derive the same word from $a^{n!}b^nc^n$. The two derivations overlap (over the middle part) and so must be “inherently” different (i.e. have different derivation trees).

Another example, from the world of regular languages, is as follows. Consider the language over the alphabet $\{a,b\}$ of all non-empty words having either an even number of $a$’s or an even number of $b$’s (or both). Does it have a disjoint representation as a union $L_1^+ \cup \cdots L_m^+$ (here $+$ is the Kleene plus)? Intuitively, the problem is that a word with both $a$ and $b$ even is “ambiguous”.

The formal proof goes by the usual pumping lemma. Pick an odd $n$ that is greater than the pumping length of all $L_i^+$’s in a given representation. The word $a^n b^{n!}$ is generated by a unique $L_i^+$. By the pumping lemma, $L_i^+$ also generates $a^{n!} b^{n!}$. Similarly, the word $a^{n!} b^n$ is generated by a unique $L_j$, which also generates $a^{n!} b^{n!}$. If $i=j$ then $L_i^+$ generates the concatenation, which has both $a$ and $b$ odd – so $i \neq j$ and we get inherent ambiguity.

A grammar said to be ambiguous if it has multiple derivations for a word. if there are 1000 word for which grammar has unique way , but even for one word it has more than one path it will said to be ambiguous.

Lets look in the following examples :

Example 1 :

S -> XaaX/ aX

X -> Xa/Xb/ ^

let us drive one word “aabaa” from two ways:

S => XbaaX

=> Xa baaX

=> Xa abaa ^

=> ^aabaa

=> aabaa

S => aX

=> a Xa

=> a Xa a

=> a Xb aa

=> a Xa baa

=> a ^ abaa

=> aabaa

Example 2:

S → AB | C

A → aAb | ab

B → cBd | cd

C → aCd | aDd

D → bDc | bc

now we will drive aabbccdd from two ways

S => AB => aAb cBd => aabbccdd

S=> C => aCd => aaDdd => aa bDc dd => aab bc cdd => aabbccdd

- Derivatives and Integrals of Polynomials and more.
- On maximal submodules of projective modules
- Applications of cardinal numbers
- Spectral measures
- Proving $\sum_{k=1}^n k k!=(n+1)!-1$
- On the order of elements of $GL(2,q)$?
- Orthogonal projections with $\sum P_i =I$, proving that $i\ne j \Rightarrow P_{j}P_{i}=0$
- where can i find this A.H. Stone's theorem proof?
- How to understand compactness?
- Given a matrix with non-negative real entries, can you algebraically prove that it has a non-negative eigenvalue?
- Greibach normal form conversion
- Circle Packing Algorithm
- Evaluating the limit: $\lim\limits_{x \to \infty} \sum\limits_{n=1}^{\infty} (-1)^{n-1}\frac{x^{2n-1}}{(2n)! \log (2n)}$
- Show that something is a group.
- Sanity check about Wikipedia definition of differentiable manifold as a locally ringed space