Hot answers tagged

4

There is a large number of mathematical topics related to finite automata and regular languages, but to start with, I would suggest to write a clean mathematical approach to the basic notions and results, like the minimal automaton and Kleene's theorem. My first recommendation would be to avoid most of the classical books on automata theory, which are ...


4

You'll need a start state that can lead into two paths, one of which accepts $ab$, the other of which accepts $ba$. You should be able to construct a NFA from that; I'm not sure what the "NFA myth" is.


4

It's a trick answer: your states don't have to form a connected graph. (i.e. the states don't all have to be reachable from the start state). So take any 1-DFA, add an accepting state that isn't connected to anything, and, hey, it's a 2-DFA.


3

PDA for $\mathcal L=\{a^nb^n|a,b\geq0\}$ Instand of $n\neq 100$ I will take $n\neq 3$ and you can do the same for $n\neq 100$ PDA for $\mathcal L=\{a^nb^n|a,b\geq0,n\neq 3\}:$


3

HINT: You can use the pumping lemma to show that $L$ is not context-free. Suppose that it is, and let $p$ be the pumping length. Let $s=0^p1^p01^p$; clearly $s\in L$, so $s$ can be decomposed as $s=uvwxy$ in such a way that $|vwx|\le p$, $|vx|\ge 1$, and $uv^kwx^ky\in L$ for each $k\ge 0$. Show that the substring $vwx$ of $s$ must be a substring of one of ...


2

$\mathcal L=\{0^{i}1^{j}0^{j}1^{k}0^{k}1^{i} | i,j,k>0\}$ is a context free language? Yes, here is a grammar that will generate the language: $$S\to 0A1\\ A\to 0A1|B\\ B\to CC\\ C\to1D0\\ D\to1D0|\varepsilon$$


2

You have this grammar: $$\begin{align*} &S\to bS\mid aA\mid\epsilon\\ &A\to aS\mid bA \end{align*}$$ Let’s see what a derivation must look like. You can start by applying the production $S\to bS$ any non-negative number of times, say $k$ times. After that you can end the derivation with $S\to\epsilon$, or you can apply $S\to aA$; let’s look at the ...


2

Let $q_0$ be the initial state of a DFA accepting $\mathcal L$. Suppose that the DFA has exactly two final states. Let $q_1 = q_0 \cdot 0$, $q_2 = q_0 \cdot 00$ and $q_3 = q_0 \cdot 0000$. Since $0$, $00$ and $0000$ are in $\mathcal L$, the states $q_1$, $q_2$ and $q_3$ are final. Therefore two of them have to be equal, since there are exactly two final ...


2

Try this automata, it is deterministic and this is a private case of non deteministic , so it is also non deteministic by defenition that accepts the language $\mathcal L=\{ab,ba\}$


2

HINT: Take $m=2n$, so that $w=a^{2n}b^{6n}$. Then the lemma tells you that $w$ can be decomposed as $uzv$ in such a way that $|u|<n$, $|z|\le n$, and $uz^pv\in L$ for all $p\ge 0$. Notice that this implies that $|uz|<2n$, so $uz$ must be part of the string of $a$s in $w$. What happens now if you take $p\ne 1$? Is it actually still true that $uz^pv\in ...


1

Your current grammar will not work because it only allows for a single $a$ on the left side. You could allow for more $a$'s on the left side with the rule: $$A \rightarrow aB|aA|B$$ but then we would be allowing an infinite number of $a$'s on the left side. Here's a hint: $\mathcal{L}$ is the concatenation of two context-free languages.


1

Arbitrary means arbitrary. That means that we put no restrictions on the number, but still each number is finite and has finite length. This means that we a priori can't assume that it has less than, say $1234$ digits. All we can know is that if we start in one end it and step through we will eventually reach the other end. Whether you can add them by a ...


1

The reversal of $1001$ is $1001$. (You could have chosen a better example!) $0110$ is the complement (or ones' complement) of $1001$.


1

If $w = a_1a_2 \cdots a_n$ is a (binary) word, then $w^R = a_n \cdots a_2a_1$. If $L$ is a set of words, then $L^R = \{w^R \mid w \in L\}$. Therefore, $\{0,1,1001\}^R = \{0,1,1001\}$.


1

You are right about the statement for regular languages. This is a well known fact usually expressed by the phrase that regular languages are closed under square root (quite unfortunately, the operation you are describing is sometimes even denoted by $\sqrt{A}$) – the details of the proof should be easily googlable. The case of context-free languages ...


1

Not quite sure about what you denote by $L_f(M)$, but I assume that it is the language accepted by a PDA by a final state. I will also assume that the $\delta$ from the $M'$-tuple is meant to be $\delta'$. The more-or-less standard approach to this problem is to simulate automata $M$ and $A$ simultaneously on the given input. This means that $M'$ should ...


1

The question is answerable if you say that an $x$-block is a contiguous (though not necessarily maximal) sequence of $x$ 5's in the decimal expansion of $\pi$. For example, if the decimal expansion of $\pi$ contained $\dotsc 555\dotsc$, then we would say that $\pi$ contained a 1-block, a 2-block, and a 3-block. Under this interpretation, the answer to your ...


1

Given an alphabet $\Sigma$ the Kleene star $\Sigma^*$ is defined as the language containing all words that can be constructed from $\Sigma$. The Kleene plus is defined as $\Sigma^*$ without the empty word: $\Sigma^+ := \Sigma^* \setminus \{\varepsilon\}$


1

Your argument has a flaw. Consider for instance the language $L = \{a^n\#b^n \mid n \geqslant0\}$. Then, for each $x \in \Sigma^*$, there is at most one $y$ such that $x\#y \in L$. However, $$ \{y \in \Sigma^* \mid x\#y \in L \text{ for some }x \in \Sigma^*\} = \{b^n \mid n \geqslant 0\}. $$ Indeed, if $y = b^n$, there exists some $x \in \Sigma^*$ (namely ...


1

Your solution looks correct, If you are looking for a formula For $k$ states and $i$ input alphabets $$k^{ki+1}\times 2^{k}$$


1

I assume you ask for the meaning of $L^R$. $$ L^R = \{ w^R \mid w \in L \} $$ where the word reversal might be defined like \begin{align} \epsilon^R &= \epsilon \\ a^R &= a \quad (a \in \Sigma) \\ (a w)^R &= w^R a \quad (a \in \Sigma, w \in L) \end{align} The RHS reversed production rules should do the job: \begin{align} S &\to A S\\ A ...



Only top voted, non community-wiki answers of a minimum length are eligible