Hot answers tagged

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\}:$


2

Yes, I think you meant the correct thing, but you should write $$\{w \in \{0,1\}^* \space | \space w \text{ contains at least 3 0's}\}.$$ As a regular expression, this can be expressed as (as adjan has already done) $$1^*01^*01^*0(0|1)^*$$


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

Hint 1. Does any prefix of $a^nb^n$ satisfies your condition? EDIT (in answer to your comment) Hint 2. Consider words of the form $(ab)^n$. Do they belong to $L_1$? You should first try to solve your exercise with the bounds $1$ and $-1$ instead of $10$ and $-10$.


1

Construct an automaton that recognizes $L_1$. The idea is as follows: The automaton must keep track of the running total $|u|_a - |u|_b$ as you go along the word (i.e. $u$ is the part of the word that the automaton has read up to now). If at any point, this running total runs strictly above 10 or below -10, the word can not belong to the language anymore, ...


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

The Pumping Lemma is a statement true of all regular languages. However, it is not necessarily false for irregular languages. In general, the Pumping Lemma is used to prove something must be irregular. It cannot be used to prove something is regular, because of exactly this example. This is analogous to saying "9 is odd and greater than 2! Why isn't it ...


1

HINT: If $p$ is the pumping length, start with $s=0^p10^p1$ and pump down.


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 general method is to convert the two regular expressions to a finite automaton each and compare those. In detail: Convert a regular expression to a non-deterministic finite automaton (NFA), e.g. via Thompson's construction Convert a NFA to a deterministic finite automaton (DFA) via power set construction Apply DFA minimization to a given DFA to get a ...


1

If $L$ is a regular language, then it is defined by an extended (right-) regular grammar (see https://en.wikipedia.org/wiki/Regular_grammar) $G$, whose rules are of the form: $B\to w$, for $B$ a nonterminal symbol, $w\in \Sigma^*$ (a string of terminal symbols); $B\to wC$, for $B,C$ nonterminal symbols, $w\in \Sigma^*$; $B\to\varepsilon$. Given ...


1

$zyyzy$ does belong to the language but not $zyyxz$ Edit : in $zyyzy$ can be split into two : $zyy$ and $zy$ which both belongs to $zy^*$ and therefore $zyyzy$ belongs to $(x^*y|zy^*)^*$


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

Hint: Assuming that $|w|_0<|w|_1$ means that the number of one's $>$ number of zero's $$A_2=\{w001;|w|_0<|w|_1 \wedge w\in \small\sum^{\quad *} \}$$ Let us choose the word $z=1^p$ so $1^p001\in A_2$ Spoiler:



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