# Tag Info

3

Suppose that $w$ is in the language. We can write $w$ as a concatenation of runs: $$w = a^{i_1} b^{j_1} a^{i_2} b^{j_2} \dots a^{i_m} b^{j_m},$$ where all indices other than possibly $i_1,j_m$ are strictly positive. A word of this form belongs to $(a^nb^n)^m$ if all indices are equal. Since $w$ is in the language, there must exist two indices which are ...

2

No. The language of palindromes over any alphabet with at least two elements is not deterministic, and thus has no LR or LL grammar. The language of even-length palindromes $L_{epal}=\{ww^R \mid w\in\Sigmạ^*\}$ is a classic example of a non-deterministic context-free language, and you can find the outline of a proof in Hopcroft & Ullman (and other ...

2

Although the problem of detecting whether a grammar is ambiguous is, in general, undecidable, for toy grammars like this it is usually pretty easy to find ambiguities by simply enumerating the possible (left-most) derivations until you derive the same sentence in two ways. For example, $G_1$ has just three productions $S\to a S b \mid S b \mid c$, and none ...

2

This is a typical ambiguous grammar for arithmetic expressions. You can write different unambiguous equivalent grammars. For example, if you use the traditional precedences and associativities; \begin{align*} E &\to E + T \mid E - T \mid T \\ T &\to T * F \mid T / F \mid F \\ F &\to x \mid y \mid ( E ) \end{align*} You could also go ...

1

This is what we have at our hand. Now let us see what can be get from the second production in red. From the production in Blue we have And the parsing can be stopped using $S\rightarrow \epsilon$ So from the above two work outs we find that the $a$'s and $b$'s are properly nested. (and can be mapped to the problem of valid parenthesization ) That being ...

1

The semantic rules of the attribute grammar "compute" the value of the expression to the left in terms of the values of the expressions to the right. With a grammar for regular expressions as you propose this is straightforward, but precisely because of that this can be confusing. For instance the meaning of the rule $S_0\to S_1 S_2$ is ...

1

Any "interesting" regular expression (i.e., one that includes Kleene star) represents an infinite set. Thus to "calculate the set of all strings" won't work so well. In a sense, the regular expression is a compact description of the language. What other kind of description do you expect to construct? It is rather easy to construct regular ...

1

You seem to be looking for a deterministic procedure that isn't there. With multiple production rules, you solve in every possible way. For instance, for the grammar $S \rightarrow a \\ S \rightarrow aS$ we have $\underset{G}{S \implies a}, \\ \underset{G}{S \implies aS}, \\ \underset{G}{aS \implies aa}, \\ \underset{G}{aS \implies aaS}, \\ \ldots$

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