New answers tagged

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 ...
gnasher729's user avatar
  • 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 ...
gnasher729's user avatar
  • 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$...
Steven's user avatar
  • 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 ...
Abhinav Aryan's user avatar
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 ...
Nathaniel's user avatar
  • 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 ...
Hendrik Jan's user avatar
  • 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 ...
Steven's user avatar
  • 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, \...
Kai's user avatar
  • 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 ...
Chaos's user avatar
  • 463

Top 50 recent answers are included