The tag has no wiki summary.

learn more… | top users | synonyms

-1
votes
0answers
18 views

The max number of repeats of substrings of a sample of a language.

So we suspect that finding the smallest grammar of strings in the language $\{a^n : n \in \Bbb{N}\}$, is hard. But luckily as far as applications to natural language processing, we would rarely ...
2
votes
0answers
38 views

What is the notation for a sub-expression?

For set theory, we have notation to denote subsets, e.g.: $$S \subset X$$ When working with expressions (arithmetic, Boolean, etc.), is there a notation to denote expression $S$ is a valid ...
2
votes
3answers
48 views

Parenthesize expressions.

Can someone tell me how to add parenthesis to this expression $a + b \cdot c \cdot d + e$. where $a,b,c,d,e$ are algebraic variables, where addition and multiplication is as usual there. :-) ...
0
votes
1answer
25 views

Efficiency LL and LR parsing

My question is, is an LL parser or an LR parser more efficient (in big-O terms) ? I don't mean in terms of coding the parser, but rather in the context of the runtime of the parser. Is there a ...
0
votes
1answer
28 views

Backus-Naur Form with automata

Parsers & compilers usually utilize deterministic finite automata to parse input. It's very easy to implement a generic DFA tool, that simulates any DFA table for example to validate input. ...
0
votes
3answers
51 views

grouping non-zero entries in a matrix according to a rule

I have a matrix say, $a = \left[\matrix{ 0 & 1 & 0& 0& 0& 1& 0\\ 0& 0 &0 &0 &0 &1& 1\\ 1& 0 ...
1
vote
0answers
72 views

Eliminating Epsilon Production for Left Recursion Elimination

Im following the algorithm for left recursion elimination from a grammar.It says remove the epsilon production if there is any I have the following grammer ...
1
vote
1answer
387 views

How to prove CYK algorithm has $O(n^3)$ running time

I have a final coming up in few days, and the professor mentioned the CYK algorithm. I want to be prepared for the final. I'm trying to find out how to prove the algorithm has worst case running time ...