4
One possible grammar is:
\begin{align}
S&\rightarrow Tb &(1)\\
T&\rightarrow AXY &(2)\\
T&\rightarrow ATXY &(3)\\
YX&\rightarrow YZ &(4)\\
YZ&\rightarrow WZ &(5)\\
WZ&\rightarrow WY &(6)\\
WY &\rightarrow XY &(7)\\
AX &\rightarrow AbA_X &(8)\\
A_XX&\rightarrow A_XA_X &(9)\\
A_XY&\...
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.
3
Lemma 1: The non-contracting rule $XY\rightarrow YX$ can be rewritten as context-sensitive rules.
Proof: If that rule is the only rule in the grammar where $Y$ appears on its left-hand side, we can replace $XY\rightarrow YX$ by the following three context-sensitive rules, $XY\rightarrow NY$, $NY\rightarrow NX$, and $NX\rightarrow YX$, where $N$ be a new non-...
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
Your language is known as $L^+$.
It is a very standard property of regular languages that if $L$ is regular then so is $L^*$; this can be proved in several ways, and you can find proofs in textbooks and online sources. Since $L^+$ is either equal to $L^*$ or obtained from it by removing $\epsilon$ (the empty string), then $L^+$ is also regular.
2
To construct a DFA, note the following:
An empty string or any string containing only $0$s is accepted, so
any $0^*$ is accepted.
Zero or more $0$s followed by one or more $1$s is accepted, so any
$0^*11^*$ is accepted.
Zero or more $0$s followed by one or more $1$s followed by $0$ is
rejected, so any $0^*11^*0$ is rejected.
Any extension to a rejected ...
2
The main advantage of having a Programming Language that is not Turing Complete is that your language can be strongly normalizing, that is, you can ensure that all terms halt with a unique, well formed value.
I've come across non-Turing complete languages primarily with proof assistants. When you're using programs to prove theorems, you need to make sure ...
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 ...
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 ...
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 $...
1
No. By Greibach's theorem, it is undecidable whether a CSG generates a context-free language.
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 ...
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
That grammar has two problems.
It's ambiguous. You say that you want to give AND precedence over OR and make both operators left-associative, but your grammar does not reflect that goal since it does not distinguish AND from OR and it explicitly accepts both left- and right-associative parses:
<WORD> <OPERATOR> <LOGICAL> (* right ...
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 ...
1
The conclusion is: the languages recognized by DOCA(deterministic one counter automata) is a proper subset of the languages recognized by DPDA(deterministic pushdown automata).
The reason why Hopcroft said the proof is complex is that in his definition, the input string of DOCA is appended with an endmarker \$ [1:P356]. So, the actual difficulty is to ...
Only top voted, non community-wiki answers of a minimum length are eligible
