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 ...
user avatar
  • 33k
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, ...
user avatar
  • 24.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 ...
user avatar
  • 341
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 $...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 11k
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 $...
user avatar
  • 22.7k

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