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 ...
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 ...
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$...
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 ...
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 ...
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 ...
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, \...
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 ...
Top 50 recent answers are included
Related Tags
automata × 1773finite-automata × 798
formal-languages × 439
regular-languages × 368
pushdown-automata × 229
context-free × 223
regular-expressions × 185
turing-machines × 167
nondeterminism × 104
formal-grammars × 98
computability × 79
computation-models × 60
pumping-lemma × 59
complexity-theory × 45
algorithms × 44
closure-properties × 42
undecidability × 40
terminology × 31
compilers × 31
reference-request × 30
simulation × 29
proof-techniques × 27
parsers × 23
buchi-automata × 19
reductions × 16