New answers tagged automata
0
votes
What are the practical examples of Semidecidable problems? Is NP problem a semidecidable problem?
A problem in NP with the answer “yes” can be solved by getting a clever hint followed by a polynomial time verification.
We could solve it very very slowly by enumerating all possible hints.
Which ...
- 28.4k
0
votes
Contradiction via pumping lemma
Assume you parsed c b^(m+4) for some m. Show that different m must give different states.
You are in a state where c^(m+7) leads to an accepting state. After parsing c b^(m’+4) for m’ ≠ m the same ...
- 28.4k
1
vote
Contradiction via pumping lemma
Suppose towards a contradiction that $L$ is regular and let $p$ be its pumping length.
Consider the word $w = cb^{4+p}c^{7+p} \in L$. By the pumping lemma, $w$ can be written as $xyz$ with $|xy| \le p$...
- 28.5k
0
votes
Constructing a PDA for the language $\{a^mb^n | m > n\}$
According to me if no. of a's is greater than no. Of b's and once the pushing of string a is completed in the stack then we start popping out every a for every b we get,then at last more than 1 no. Of ...
1
vote
Accepted
Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL
In the last case, you should consider $uxz$. It is useful to note that $(N-1)^2 < N^2 - N$ if $N > 1$.
Indeed, if we suppose $v= 0^r$ and $y = 1^s$, with $r > 0$ and $s>0$, we also have $r ...
- 12.5k
0
votes
Informal description of Non-deterministic TM for the language $L = \{w^n \mid w \in \{a, b\}^* \text{ and } n \geq 2\}$
When "marking a letter" on the Turing tape, we replace a symbol $a$ by another symbol, like $X$, $\bar a$, or $\underline a$. Since various markings might be needed it is practically more ...
- 29.9k
2
votes
Accepted
Is L={0^n 1^n ∣n≥0} context free language?
You have just shown that the given language does not meet the condition of the pumping lemma for $n=5$ and one particular decomposition.
To conclude that $L$ is not context free you need to show that ...
- 28.5k
0
votes
Accepted
How to find prefixes and suffixes for infinite languages? (Automata)
For regular languages this is relatively straighforward. Let $L\subseteq\Sigma^*$ be regular. Let $A = (Q, \Sigma, q_0, \delta, F)$ be an NFA that recognises $L$. Construct another NFA $A' = (Q, \...
- 663
0
votes
How to find prefixes and suffixes for infinite languages? (Automata)
Let's see what others say but
I think you could adapt the algorithm that enumerates the sentences of a language and restrict it to enumerate prefixes or suffixes only. I assume you are familiar with ...
- 463
Top 50 recent answers are included