New answers tagged automata
1
The language is finite and, as such, it is regular (all finite languages are regular).
To see that the language is finite, notice that the maximum length of each word in $L$ is upper bounded by $500$.
Indeed, if $w \in L$, and $n$ (resp. $m$) is the number of $a$s (resp. $b$s) in $w$:
$$
2|w| = 2(n + m) \le 2n+ 3m \le 1000.
$$
1
First to clear up: $w$ is not a language, it is an arbitrary string composed of the symbols $0$, $1$. The "plain English" definition of this language would be "all binary strings that can be expressed as two or more repetitions of any binary string (including the empty string)".
Examples of strings that are members of this language would ...
1
Suppose towards a contradiction that your language $L$ was regular and let $p$ be its pumping length.
Consider the word $w = 0^p 10^p1 \in L$. By the pumping lemma, $w$ can be written as $w=xyz$ with $x=0^{h}$, $y=0^k$, and $z=0^{p-h-k}10^p 1$ (here $h+k \le p$ and $k \ge 1$) such that, for every non-negative integer $i$, $xy^iz \in L$.
Substituting and ...
2
For an integer $n$, consider the following DFA $A_n$ on the alphabet $\{a\}$. The set of states is $\{q_0,\ldots,q_{n-1}\}$. The initial state is $q_0$. All states are accepting. The transition function is $\delta(q_i,a) = q_{i+1}$, where we identify $q_n$ with $q_0$.
Do the relations of $A_2$ and $A_3$ refine each other?
0
Yes, the DFS is an algorithm, and hence has an equivalent turing machine. The definition of the decidability as you have said, is for the language to be exactly accepted by some turing machine.
The formal definition of the turing machine accepting the language of strongly connected graphs probably is waaaay too hard to explicitly write, so I guess your ...
1
Depending on the algorithm to convert it.
We can construct an algorithm to convert an NFA to a regular expression by first converting it to a DFA, and then the DFA to a regex. This will yield that the regex for the DFA would be identical to that of the NFA (by definition of the algorithm)
But, you might find some other way to directly convert an NFA to a ...
1
For any DFA, NFA or regular expression, there is only one corresponding language. But for one language, there can be multiple corresponding DFA's, NFA's or regular expressions, so it is incorrect to talk about "the" regular expression of a DFA, but would be correct to say "a" regular expression associated to a DFA.
If you know a regular ...
1
You say you are familiar with the standard subset construction that turns an NFA into a DFA. Let's start from there. If you study some examples you may realize that the result is not optimal. By "trimming" you might obtain a "better" DFA that still is equivalent.
In the first example you see that not all sets in the construction are ...
1
There is more than one DFA. Just add a useless state with transitions from it to the other states. With no way to reach this useless state, the new DFA will be equivalent.
There are in fact an infinite amount of equivalent DFA's.
1
Denote your language by $L$.
Suppose that the pumping length is $p$. Consider
$$
N = (10^{p+1} + 1)^3 = 10^{3p+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1,
$$
whose decimal encoding is
$$
w = 1 0^p 3 0^p 3 0^p 1 \in L.
$$
According to the pumping lemma, we can write $w = xyz$ so that $|xy| \leq p$, $y \neq \epsilon$, and $xz \in L$. Since $|xy| \leq p$, ...
2
Your grammars for $A_1$ and $A_2$ seem correct. Since you want to compute the concatenation of $A_1$ and $A_2$, you just need to express this fact with the start symbols of $A_1$ and $A_2$.
$S \rightarrow S_1S_2$ is a way to do it.
You can check by computing the derivation that creates the word $001110$.
0
For any c.e. collection of c.e. sets, the union is c.e., however if the collection itself is not c.e, then not (a counterexample is $S_x = \{x + n : n \in \mathbb{N}\}$, then $\bigcup_{x\in\mathbb{R}} S_x$ is not c.e. even though it's a union of only c.e. sets).
To see the above by explicit construction, first if you allow duplicates in your enumeration (...
2
Every language can be written as a countable union of singletons $\{x\}$.
On the other hand, the union of finitely many c.e. languages is c.e.
2
You can use the pumping lemma to prove that the language is not context-free. Suppose $B$ is context-free and let $n$ be the constant of the pumping lemma. Consider the word $u = 0^n1^n2^{n^2+1} \in B$. Then we can write $u = vwxyz$ such that:
$|wxy| \leq n$;
$|wy| > 0$;
$\forall k\in \mathbb{N}, vw^kxy^kz \in B$
Now since $|wxy| \leq n$, we either have ...
1
In a related question you obtained a context-free grammar for this language.
$S\to bSa \mid A\mid B$
$A\to aA \mid a$
$B\to bB \mid b$
Although I agree with Yuval that directly constructing a push-down automaton shows you understood the concepts of a PDA, I like to recall that there are direct constructions between PDA and CFG. As wikipedia mentions the ...
1
The PDA has two main states:
No $a$ has been encountered.
Some $a$ has been encountered.
While in the first state, it pushes $B$ onto the stack for any $b$ it encounters. It moves to the second state when encountering an $a$, at which point it removes $B$ from the stack for any $a$ it encounters (including the first $a$). If it ever realizes that it has ...
4
A word in $L$ must either be of the form $b^i a^j$ with $i \neq j$ or it must have $ab$ as a substring.
Therefore you can write a context-free grammar $G$ for $L$ as the union of two context-free grammars $G_1$ and $G_2$ for $L_1 = \{b^i a^j \mid i \neq j\}$ and $L_2 = \{w \in \{a,b\}^* \mid ab \mbox{ is a substring of } w\}$.
It is easy to come up with a ...
1
In the standard definition of a finite automaton (say a DFA or an NFA), the alphabet is a non-empty finite set (perhaps the empty set is allowed by some definitions). The reason we insist that the alphabet be finite is that otherwise the description of the automaton would potentially not be finite.
For example, in one common definition of DFAs, the ...
1
This is probably a better and clearer solution using the Myhill-Nerode Theorem. As there are infinite prime numbers, so for the sake of contradiction, let us assume that the language has finite classes. Thus there exist at least two primes $p_1$ and $p_2$ (wlog $p_2 > p_1$) such that $$[a^{p_1}]_{\equiv_L} = [a^{p_2}]_{\equiv_L}$$
Now, using the right ...
9
No, that's the language containing one string: the empty string, which is very much distinct from the empty language. The finite state machine on the left accepts language $\{\}$, the finite state machine on the right accepts language $\{\varepsilon\}$. They are not the same.
If a lot of students are confused maybe explicitly show the difference in an ...
1
The language $S = S_1 \circ S_2$ (I'm assuming that was the intended notation) is in NP if $S_1,S_2$ are in NP. Indeed, given verifiers for $S_1,S_2$, we can construct a non-deterministic verifier for $S$ as follows:
Given an input $x \in \{0,1\}^*$, guess a decomposition $x = x_1 \ldots x_n$ for even $n$, and use the verifiers for $S_1,S_2$ to verify that $...
2
Brzozowski's paper on arXiv might have a full account of the algorithm. He's one of the pioneers in what I've termed the "algebraic approach" for formal language and automata theory - best known for invoking the "Brzozowski derivative" (aka left-quotient) to describe the state transition of a regular language in algebraic terms. It's the ...
4
The intuition is that the strings of a context-free language are formed by the "frontier" (the leaves) of the derivation trees. The trees themselves are no longer directly visible.
Thus, the intersection of two tree languages consists of the trees the structure of which belongs to two tree grammars. We must be able to map productions of both ...
Top 50 recent answers are included
