New answers tagged automata
1
Apply the pumping lemma on the word $b^nc^n$.
0
No, there are no other possibilities as far as I can see.
The ambiguity comes from the production rule $expr \rightarrow expr - expr$. This rule allows you to derive the expression in two different ways:
Derive $1$ from the left $expr$ and the rest from the right $expr$
Derive $1-2$ from the left $expr$ and the rest from the right $expr$
Some ideas that ...
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 ...
4
The standard example is the halting problem – the language of all descriptions of Turing machines which halt on the empty input.
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
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$...
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 ...
0
You need to design a NPDA that behaves as follows:
If it reads "a" and stack is empty push "a" onto stack
If it reads "b" and stack is empty push "b" onto stack
If it reads "a" and top entry on stack is "a" the push "a" onto stack
If it reads "b" and top entry on stack is "a" the pop "a" from the stack
If it reads "a" and top entry on stack is "b" the pop "...
0
The powerset construction shows that for every NFA with $n$ states there is an equivalent DFA with $2^n$ states. Every example in which this is tight – that is, the minimal DFA has $2^n$ states – is a counterexample to your claim. You can find such an example, for arbitrary $n$ and over a binary alphabet, in this answer.
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$, ...
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$ ...
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 ...
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.
Top 50 recent answers are included
