4
The standard example is the halting problem – the language of all descriptions of Turing machines which halt on the empty input.
2
Start with a long enough string $w$ in $L$ in which $m=p+2,n=p+1,o=p$ and
$i_1,...,i_{2m}=0$
$j_1,...,j_{2n}=0$
$k_1,...,k_{o}=0$
$w = a\; b^{2(p+2)}\; d\; e^{2(p+1)}\; g\; h^{p} $
Then apply pumping lemma (it should be easier ;-).
If you want to "reduce" $L$ to $L' = \left\{0^i1^j2^k|1\le \:i<j<k\right\}$ then you must use closure properties, in ...
2
No, there aren't always unreachable states. Consider the NFA with one state, $q$, and no transitions. (It accepts the language $\{\epsilon\}$ if $q$ is accepting, and accepts $\emptyset$, otherwise.)
If you determinize this automaton, you end up with a two-state DFA with a transition from the start state $\{q\}$ to the other state, $\emptyset$, ...
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 $...
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
I read some references in order to answer your question ,
Transition function : takes as arguments a state and an input symbol and returns a state, denoted by δ .
Extended transition function : Describes what happens when we start in any state and follow any sequence of inputs ,means is a function that takes a state q and a string w and returns a state p (...
1
Apply the pumping lemma on the word $b^nc^n$.
1
If I understand your argument correctly, you are reducing languages in the wrong direction.
If $L$ is not context-free, then $K$ is not context-free.
Is equivalent to
If $K$ is context-free, then $L$ is context-free.
We have to reverse the construction, as we are using the closure properties of the context-free languages. In do not know of any useful ...
1
Let us check the first part, $L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$ where $m>n>o>0$, $i_1,i_2,...,i_{2m} \geq 0$, $j_1,j_2,...,j_{2n} \geq 0$, $k_1,k_2,...,k_o \geq 0$. Note the "where" clause means $\#_b(w)$ and $\#_e(w)$ are even and $\#_b(w)>\#_e(w)>2\#_h(w)$.
Assume $L$...
1
The rule for the $\sigma\in \Sigma$ must be applied each time a letter appears in the regular expression, not only once per letter : you must build a different automata each time the letter appears. If you see it as some kind of digital circuit, you do not want to use the circuit that recognizes $a$ in $ab$ for the circuit that recognizes $a$ in $a + \...
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$ ...
Only top voted, non community-wiki answers of a minimum length are eligible
