Tag Info

New answers tagged

1

The easiest way to deal with $A$ is to realize that it has a simpler description: $$A=\{u1v:u,v\in\Sigma^*\text{ and }|u|,|v|\ge 1\}\;.$$ Once you see this, it’s very easy to write down a context-free grammar for $A$. To show that $B$ is not context-free, use the pumping lemma with the word $s=0^{p+2}10^p10^{p+2}$, where $p$ is the pumping length. You’ll ...


0

There is a small correction to be made in part 3 of your proof. The string can be divided in may ways, $xy$ is not necessarily $0^{p}$ but it is true that the string $xy$ consists of only zeroes, so $y$ consists of only zeroes. That could also be just one zero, for instance. The 'unused' zeroes end up in z. But for whatever number of zeroes $y$ has, pumping ...


0

I would suspect just mentioning a string and the pumping lemma is not a full proof that you found a string that cannot be pumped in any way. This is my try: The string $01^{p}2^{p}$ can be divided in three parts $x$, $y$ and $z$ only in these ways: 1) $x = \epsilon$, $y = 01^{a}$ $|$ $a \geq 0$ If x has length zero, y will always be a zero and some ...


0

A conceptually simple way to do this depends on whether you can perform two transformations of FAs. We'll get to that in a bit. Step 1. Your first step is to make a FA for the language of strings presented from most significant bit to least significant. Suppose you wanted to make a FA for all binary strings which when presented from MSB to LSB represent ...


1

It suffices to be able to check divisibility by $p^k$ for primes $p$, since you can always combine a finite number of DFAs into one that essentially runs them in parallel and accepts iff they all accept. This is trivial for $p=2$. If $p$ is an odd prime, $2$ is a unit in $\Bbb Z/p^k\Bbb Z$, so there is an $m\in\Bbb Z^+$ such that $2^m\equiv1\pmod{p^k}$, and ...


2

Turing machine tapes are usually taken to be infinite in both directions, so the machine starts looking at the first input symbol, but there's an infinite supply of blanks to the left of that.


0

One way is to use the pumping lemma for regular languages; the linked article has an example of how to use it. If you try that approach with the word $w=b^pa^{p+1}$, where $p$ is the pumping length, you’ll get the desired contradiction very easily. I find this the easiest approach, but you can also use the Myhill-Nerode theorem. If you use it, you might ask ...


0

Yes, the second DFA cannot take a word $aaaa$ as it is the language of words with at least two b's with no restriction on the number of $a$'s. Moreover, the first graph is wrong it accepts the language of exactly two $a$'s.


0

"Final state" is a confusing term. It does not mean that the state is actually the last one, or that the automaton stops when it reaches the final state. It means that if the automaton reaches that state at the end of the input, then the automaton will accept the input. The automaton might reach a final state at the end of the input, or it might not. For ...


0

Note: Maybe you have to clarify whether the PDA is deterministic. Here my answer is based on non-deterministic PDA, or simply CFG. For a $w\in\{a,b\}^*$, define $$D_i=\#(a,w[1,i])-3\#(b,w[1,i])$$ and consider the grah of this sequence. The trick here is always thinking of the first time when the polyline of $D_i$ comes across a certain horizontal line. For ...


0

For the first part of the conditions, i.e. $|w|_0\equiv 0 \pmod 2$, you need two states, one for when the number of $0$'s read is even and one for the odd. For the second one, you must create a help state for the two states you had that reads the $1$ and pushs the 0 for the other state. So the problem is that you are thinking in just keep 2 states. And you ...


1

The languages recognized by non-deterministic PDAs are precisely the context-free languages, so the answer is yes for them. In this case you can even do it with a deterministic PDA: essentially all you need to do is push left brackets onto the stack and pop the top of the stack when you read a right bracket, if the top of the stack is the same kind of ...


1

An NFA accepts a word $w$ if $w$ governs at least one path from the initial state to an acceptor state. Thus, your second automaton accepts every non-empty word in $\{0,1\}^*$: every such word can reach $q_1$ (though of course it needn’t).



Top 50 recent answers are included