# Tag Info

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