# Tag Info

### 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 ...

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 ...
1 vote

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$...

### 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