New answers tagged automata
1
While solving common programming tasks it's usually not helpful to think of an automaton. But there are still many cases where they are applied:
writing small parsers (e.g. parse an integer/float); in order to not forget edge cases drawing an automaton is really helpful; for more complicated parsers grammars are usually a better tool
state machines are ...
0
Suppose that $w = ncm$, where $n \neq m^R$, say $n$'th $i$-th letter from the left, $\sigma$, differs from $m$'s $i$-th letter from the right, $\tau$. Then
$$
w \in \Sigma^{i-1} \sigma \Sigma^* c \Sigma^* \tau \Sigma^{i-1},
$$
where $\Sigma = \{a,b\}$. Conversely, every $w$ of this form is in your language. You take it from here.
0
This answer is for the original version of the question, in which "$k$" was missing.
Your language contains all non-empty words. Indeed, if $w \neq \epsilon$ then you can write $w = nm$, where $m = \epsilon$ and $n = w \neq \epsilon = m^R$. In contrast, if $\epsilon = nm$ then $n=m=\epsilon$ and so necessarily $n=m^R$.
3
A decision tree is a model of computation which makes sense for instance of constant size. In contrast, a language is usually a collection of instances of unbounded size. An automaton (in this context) is a model of computation which describes a language.
The upshot of all this is that in most circumstances, it doesn't really make sense to convert a decision ...
1
The unequal number of $a$'s and $b$'s have
{equal number of $a$'s and $b$'s} with {{extra $a$'s } or {extra $b$'s}}
Extra $a$'s or extra $b$'s can be
at the beginning
at the end
in between (ANY WHERE) and any number of times
Let $P$ derive strings with extra $a$'s
Let $Q$ derive strings with extra $b$'s
Let $X$ derive equal number of $a$'s and $b$'s
Let $A$...
0
Let's do the first one. You want to find what condition on $b$ will imply $2(b-1)-1>0$. All you have to do is solve this inequality.
The other ones are similar.
1
In order to show that $f$ is regularity preserving, it suffices to show that $f^{-1}(U)$ is eventually periodic for $U = \{ n : n \equiv b \pmod{a} \}$, where $a$ is a prime power (here we are using the Chinese remainder theorem and the fact that the eventually periodic sets are closed under intersection).
For $f(n) = 2^n$, we consider two cases:
If $a = 2^...
1
Hint:
0
I'll explain my thought process behind thinking about this problem here:
-> With inequalities, I first think at the equality constraint. So I assume n = m+3
-> Now, n is always 3 more than m.
-> I split the problem further. I think to myself okay, let's have one production handle equal production of a and b.
-> How many more b's do we need after ...
0
This is a common question regarding pumping lemmas, and it is completely answered by carefully understanding the quantifiers in the lemma.
The lemma itself says the following:
For every CFL $L$, there exists a constant $p$ such that for every word $w\in L$, if $|w|>p$, then there exist words $u,v,x,y,z$ such that $w=uvxyz$, and (1) $|vxy|\le p$, (2) $|vy|...
1
The best way is to learn is to look at examples, and see how they work.
One of the simplest "real" context-free languages is $\{\; a^mb^n \mid n = m \;\}$
Its grammar is $S\to aSb\mid \varepsilon$.
Now add in steps, the extra 3, and the more than ...
$\{\; a^mb^n \mid n = m+3 \;\}$
$\{\; a^mb^n \mid n \le m+3 \;\}$
0
It looks like you missed the paragraph for induction right before the Example 4.19 or figure 4.9 and the repetitive application of that induction.
INDUCTION: Let $p$ and $q$ be states such that for some input symbol $a,$ $\ r =\delta(p,a)$ and $s = \delta(q,a)$ are a pair of states known to be distinguishable. Then $\{p, q\}$ is a pair of distinguishable ...
0
(a) Let $\Sigma$ be the alphabet of $L$ and $\Sigma^*/\equiv_L$ the set of equivalence classes of words over $\Sigma$ according to the equivalence relation $\equiv_L$. Define the DFA to have one state for each element of $\Sigma^*/\equiv_L$ (we could think of the states as the classes themselves). Define the initial state to be the class of the empty word $\...
1
The basic idea is that if a regular language is infinite, then it contains a word of infinite length. Indeed, the pumping lemma shows that the set of lengths of words in the language contains an arithmetic progression, and every arithmetic progression contains a composite integer.
We can check whether the language accepted by an NFA is infinite as follows:
...
0
Let's recall the Pumping Lemma statement:
For all regular language $ L $, exists a positive constant called $ p $ (i.e. $ p \geq 1 $) such that every string $ w $ in $ L $ with length $ |w| \geq p $ exist strings $ x, y, z $ such that $ w = xyz $ and that statisfying the following conditions:
$ |y| \geq 1 $
$ |xy| \leq p $
$ xy^iz \in L, \: \forall i \geq ...
3
Here is a simple example. Take any non-regular language $N$ contained in $(aa)^+$ and consider the language $L = 1 + a(aa)^* + N$. Then $L$ is not regular since $L \cap (aa)^+ = N$ is not regular.
On the other hand, $L^2 = a^*$ is regular.
3
$(a^+b \mid b^+a)^*$. I am not sure there is a "simple" description of your language in plain English, but directly from the regex you get that it is the language that has the empty string and all strings that can be partitioned in such a way that each part is either multiple $a$'s (at least one) followed by one $b$, or vice versa.
In my opinion ...
5
Your claim is false. Indeed, it is equivalent to prove that if a language $L$ is not regular, then also $L^2$ is not regular, but this is not true. Here Yuval Filmus gives (possibly) two examples of a non regular language whose "square" is regular, namely $L = \{ 1^p \mid p \text{ is an odd prime}\}$, under the Goldbach conjecture, and $L' = \{ 1^...
2
Any language can be recognized by a Turing machine with an infinite number of states. Let the state graph be an infinite trie; scan over the input from left to right once, and you end up at a unique state for each possible input string.
By contrast, if you are familiar with different cardinalities of infinite set, it is easy to see that there must be some ...
Top 50 recent answers are included
