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