New answers tagged automata
0
Both HP and MP are decision problems, namely sets of instances that you can think of as descriptive strings. For example,
HP is a collection of pairs $M, x$ where $M$ is the description of a Turing Machine (think of a listing) and $x$ is an input to that machine. An instance is such a pair and a pair is in the set HP if the machine described by $M$ ...
0
If the machine does exacly 5 moves, it reads at most 5 symbols. If after 5 moves it is still going, it does more than 5 moves on a tape starting with that string. So you have to check a finite set of possible inputs (strings of 5 symbols), each for a finite number of steps (5 in this case). So you can always answer "yes" or "no" in finite time, this is ...
1
I think that you are having trouble distinguishing the difference between regular and non-regular languages, so I try to give a short explanation before I give you an example.
We call a language $L$ regular if it can be decided if a word is in the language with
an algorithm/a machine with constant (finite) memory by examining all symbols
in the word one ...
2
I think the PDA would stuck as to accept the input string "abcd", the complete input string needs to be read. But your PDA will work only till 'c' is read and get stuck when it finds another letter 'd', but has no transition state.
0
By Rice's theorem, it is undecidable if $M$ accepts a language with a non-trivial property (there are languages that have the property and others that don't). "Includes a string starting 101" is a non-trivial property.
1
Let L = a*b. LL is regular ($a^nba^mb$). But the language you are asked to check is $a^nba^nb$ where the two n’s are the same. There are plenty of proofs in the last days here that you can adapt. And Myhill-Nerode is super easy.
0
To write the reverse of a DFA, Change all the initial states to final and the final ones to initials(for the later, if there are multiple final states, use a new state and use null transitions to each of them). At last... Reverse the edges.
2
This is one of those trap questions where $L_2$ can actually be written in a different way that makes it obvious that it is a regular language. See if you can figure out what $L_2$ is "really doing", and the answer will become obvious.
Solution:
1
No, in general. If $\bar{L_2}$ and $L_4$ are both the empty language, or have an empty intersection, then $L_4\cap\bar{L_2}\cap\bar{L_1}$ is regular, but that says nothing about whether $L_1$ is regular.
0
Just as a hint, the general way to solve a problem like this is to write a truth table. The "inputs" to the truth table are the inputs to the machine plus the states of the flip-flops (one bit per FF), and the "outputs" are the outputs of the machine and the outputs of the flip-flops.
From that truth table, you can see if it's a Mealy machine. And given the ...
1
Have a good look to the answer you link to. It specifies the language that is generated using two numbers $k,\ell$. These numbers guarantee that the two parts are different without ever knowing where the middle of the string exctly was. I will try to explain.
We have to find (or better, guess) a position in $x$ such that the same position in $y$ carries ...
1
There is a big difference between $\{ xy ∣ |x| = |y|, x = y \}$ and $\{ xy ∣ |x| = |y|, x \ne y \}$. In the first one, we need every symbol in $x$ to be the same as the corresponding symbol in $y$. For inequality, it suffices that at least one symbol in x be different from the corresponding symbol in $y$. The two cases are not symmetrical.
Checking that ...
2
$A_1$ is regular, since regular languages are closed under intersection and complement, and $A_1 = A \setminus B^{R} = A \cap (B^{R})^{c}$. To show that the reverse $B^{R} = \{x^{R} : x \in B\}$ of a regular language $B$ is regular, take some deterministic finite state machine $M$ with language $B$. Construct a new nondeterministic finite state machine $M'$ ...
13
The DFA performs a single state transition on each read input symbol, reads each symbol of the input exactly once, and halts when the input string is exhausted. In order for an infinite loop of state transitions to happen, the input string has to be infinite. DFAs are usually defined for finite inputs only, as the automaton's output is defined by what state ...
27
A deterministic finite automaton can only go to infinite loop if the input string is infinite. For finite inputs, the automaton stops when the input string ends. For infinite inputs, for example the automaton for regex 0*1 will loop infinitely if the input string is an infinite sequence of 0.
2
What you write is a snippet out of a recursive descent parser, one way of writing a program that parses a context free language. It is modelled on a PDA, specifically a LL(1) one. The stack is implicit in the recursive calls your parser does. Recursive descent is popular as it easy to write by hand (some tricks are needed to handle ambiguous constructs, like ...
1
The first language can be described as the set of words on the alphabet $\{a,b\}$ with an even number of $b$'s.
The second one is not the language of words on the alphabet $\{a,b,c\}$ with an equal number of $b$'s and $c$'s (this condition would define a non-regular language). You could use greybeard's description or say: the language contains the empty ...
0
Based on the book, Introduction to Languages and the Theory of Computation
, they are interchangeable terms.
...
These are examples of a type of language acceptor called a finite automaton
(FA), or finite-state machine.
1
No. The class of languages recognised by pushdown automata is the class of context-free languages, whereas the class of languages recognised by Turing machines is the class of Turing-recognizable (aka recursively enumerable) languages. All context-free languages are recognisable but the converse does not hold.
0
Use closure properties. Define homomorphisms $h_1$ and $h_2$ as follows:
$\begin{align*}
h_1(x) &= \begin{cases}
x & x \in \Sigma \\
\sigma & x = A \text{ (a new symbol)}
\end{cases} \\
h_2(x) &= \begin{cases}
x & x \in \Sigma \\
\tau & x = A
\end{cases} \...
2
There are many ways to perform this enumeration. Note first that you can count the number of cases in half by postulating that $Q = \{q_0,q_1\}$, that is, fixing which among the two states is initial; the choice doesn't matter due to symmetry. Now you are left with 16 possibilities. At this point there are many ways to cut the search space even further. Here ...
Top 50 recent answers are included
