Hot answers tagged

5 votes
Accepted

Distance Vector Routing Example

Let us review the specification of the algorithm. In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between ...
  • 35.3k
4 votes

Compiler Design Question

Your statement "Integer x;" is syntactically "identifier identifier;" which is a perfectly fine variable declaration. Semantically, the first identifier must be defined as a type, ...
  • 25.9k
3 votes

Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$

I would approach this question in this way, (k) in $\mathrm{LL}(k)$ means the number of lookaheads. The grammar of $\mathrm{L}$ here possess non-determinism. For example, if you can only see aaaa then ...
  • 339
2 votes
Accepted

Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$

Rosenkrantz and Stearns prove in their paper Properties of deterministic top-down grammars that the language $$ \{ a^n b^n : n \ge 0 \} \cup \{ a^n c^n : n \ge 0 \} $$ is not $\mathrm{LL}(k)$ for any $...
2 votes

Compiler Design Question

In ANSI C syntax, as you say, there is no such construct as Integer, but only int. So your compiler should highlight a Syntax ...
1 vote
Accepted

Remove left recursion from a grammar without necessarily removing epsilon production

If a grammar includes nullable productions, then it may have hidden left recursion; a production such as $A\to N A \beta$ where $N$ is nullable. Such a production won't be removed by Ullman's ...
  • 11.4k
1 vote

What are the maximum possible values of X and Y?

Let's try to find a feasible allocation of passengers to buses that minimizes $X$. Let's consider the ideal situation in which all non-empty buses, except possibly one, are filled with one less than $...
  • 24.2k

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