New answers tagged formal-languages
4
Logic programming with substructural logics has been studied, starting in the second half of the 90's. I am not an expert, but I can probably provide enough references to get you going.
There is Dale Miller's Lolli, a programming language for linear logic programming.
Major research was carried out by Frank Pfenning and his coworkers and students. For ...
1
No. By Greibach's theorem, it is undecidable whether a CSG generates a context-free language.
0
Grammar should follow below rules to be LL(1)
It should not be Ambiguous.(Remove Ambiguity)
It should not be Left Recursive.(Remove Left Recursion)
It should not be a Non-deterministic.(Apply Left Factoring)
If any of the above rule is not satisfied then grammar is not LL(1). But if grammar follows all of above rules then we have to check following thing
...
2
To prove that the classes $C_k$ are equivalence classes for the Myhill-Nerode relation we need to show
For any strings $x,y \in C_k$ there does not exist a distinguishing extension of $x$ and $y$. This proves $C_k \subseteq [w]$.
For any $x \in C_j$ and $y \in C_k$ there does exist a distinguishing extension. Since every string $\omega$ belongs to some $...
3
To your first question, the answer is affirmative:
On one hand, a task that only takes polynomial time can only take polynomial space, and many among them only take linear space, so there definitely exist tasks which take linear space and polynomial time.
On the other hand, that doesn't mean every task that takes linear space takes only polynomial time. ...
2
It depends what you mean by build a parse tree.
You can build a parse forest in $O(n^3)$ time and space. The forest represents all parse trees, even an infinite number of parse trees, because it is a graph, not a tree. From a parse forest, it is possible to produce a single parse tree in time linear to the size of the forest, and it is possible to iterate ...
4
The complement of a context-free language $L$ is not necessarily context-free, but it is the difference between two context-free languages ($\Sigma^* - L$). (Here $\Sigma$ is the alphabet of $L$.)
See, for example, Is the complement of { ww | ... } context-free? for an example of a context-free language whose complement is not context-free.
0
As dkaeae indicated in his comment, a right-moving or staying Turing machine (TM) is essentially a finite deterministic automaton (FDA). Here's a proof.
Let $M$ be such a machine, whose transition rules is in the form of $\delta(q, \gamma)=(t, \beta, d)$ where $q$ is the current state, $\gamma$ is the contents of the current cell, $t$ is the new state, $\...
1
This inherently depends on your exact model of a TM, I'm assuming the following:
A left-bounded tape, the head starts at position 0 and the word to decide is written at the tape. Furthermore, the TM has finitely many states.
Now the TM can only look at the first symbol at a time, can do finite computation (i.e. can have finitely many transitions to ...
2
$\langle x \rangle$ simply denotes the encoding of some object $x$. $x$ can be a TM (e.g., its Gödel number), a string, some combination thereof (properly separated), or even other objects like a graph, etc.
This serves, for instance, to distinguish between $\{ \langle M \rangle \mid \text{$M$ is a TM} \}$, which contains encodings of TMs (e.g., their Gödel ...
0
Suppose $L$ is context free. Then, by pumping lemma, there exist two integers $h \ge 1$ and $1 \le x \le \min\{h!, c_L\}$, where $c_L$ is a constant depending on $L$, that satisfy the following:
$a^{h!} \in L$
$a^{h!-x} a^{xn} \in L$ for every $n \ge 0$.1
Now you only need to show that, for some value of $n$, $a^{h!-x} a^{xn} \not\in L$.
Equivalently, you ...
1
When we use left factoring (or any other approaches) to eliminate conflicts from LL parsing table, it becomes valid LL grammar, and hence also a valid LR grammar.
To say that the grammar "becomes a valid LR grammar" implies that it was not a valid LR grammar before. But I will argue that if a mechanical procedure is used to transform a non-LL grammar $G$ ...
1
I like the feature sensitive grammar notaion, means for each term is a set of features assigned, what must be matched inside a rule.
The rule will be just:
S[a_count = n]-> a{n}b a{n}b a{n}b ,
Compare it to notations above with 10 rules.
While matching the feature rule, parser will mach amount of a's and assign the value to S.a_count field. Dont forget, a ...
Top 50 recent answers are included
