Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now
7

The same "argument" would show that $\mathbb{N}$ is finite since it's the union of finite sets $$\mathbb{N}=\{0\}\cup\{0,1\}\cup\{0,1,2\}\cup ...$$ The point is that knowing that a given property is preserved under a given operation does not mean that it's preserved under "infinite iterations" of that operation.


4

Notice the abuse of notation used. The quote overload symbol $f$ with three meanings which I will now denote differently with $f,f',f''$. First is map from alphabet to words $$f: \Sigma \rightarrow \Gamma^*$$. The second is the map between words $$f':\Sigma^* \rightarrow \Gamma^*$$. The third is the map between languages $$f'':\mathbb{P}(\Sigma^*) \...


2

The subset of all palindromes in L is obviously not usually regular, take the simple example $a^*ba^*$ where the subset of palindromes $a^nba^n$ is not regular. Assume you have an FSM for L (that is an FSM describing and defining L). You can take that FSM and use a simple algorithm to determine if w is in M: Given a state S, define succ(S, a) as the state ...


2

Expanding on Daniel Martin's answer. None of the following interpretations yields a regular language: $L = \{ w \in \{a,b\}^* : \exists n \ge 0, \; w = a^n b^n \}$ $L$ contains all the words $w \in \{a,b\}^*$ such that the number of $a$s in $w$ is not larger than the number of $b$s in $w$. $L$ contains all the words $w \in \{a,b\}^*$ such that the number ...


2

You seem to be misunderstanding the statement of the exercise. It wants you to show that if $L$ is a language accepted by a DFA containing two states, then either $L$ is empty, or $L$ contains the empty word, or $L$ contains a word of length 1. Which of the cases holds depends on $L$. More explicitly: If no state of the DFA is accepting, then $L = \emptyset$...


2

You need to keep doing it an infinite number of times before you reach any infinite languages. So your proof will involve transfinite induction. As Wikipedia says: Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Let P(α) be a property defined for all ...


2

You proved that any finite languages are regular. All the languages that you generated are finite.


2

Since your definition of $\epsilon$-closure isn't really a definition, it is impossible to prove anything using it. Instead, let me use the following definition: the $\epsilon$-closure of a set $S \subseteq Q$ consists of all states $x \in Q$ which are reachable from a state in $S$ by a (possibly empty) $\epsilon$-path (which is a path consisting of $\...


1

Take a DFA $D_A$ for $A$ and a DFA $D_B$ for $B$. Define a DFA $D$ for $A \setminus B$ as follows: The set of states of $D$ is the cartesian product of the set of states of $D_A$ with the set of states of $D_B$. The initial state of $D$ is $(a_0, b_0)$ where $a_0$ is the initial state of $D_A$ and $b_0$ is the initial state of $D_B$. A state $(a,b)$ of $D$ ...


1

Your definition of $\epsilon$-closure is quite problematic. Here is a better formulation: $\epsilon(S)$ is the intersection of all sets $T \subseteq Q$ such that (i) $T \supseteq S$ and (ii) if $q \in T$ then $\delta(q,\epsilon) \subseteq T$. Here is a series of claims which imply $\epsilon(S) = \epsilon(\epsilon(S))$. Claim 1. $\epsilon(S) \supseteq S$....


1

For an alphabet of $\{a, b, c\}$ constructing a DFA that accepts all strings not containing the substring 'aa' tells you several things about the number of states you need. Firstly, and this is true for any DFA, you need at least one accepting state. Since your DFA is meant to filter out some strings, it requires a 'trap' or 'dead' state, a state that may ...


1

You just create a super simple Graphviz document encoding the information: $ cat foo.gv digraph { q0 -> q0 [label = "input: a\noutput: 0"]; q0 -> q2 [label = "input: b\noutput: 0"]; q1 -> q1 [label = "input: a\noutput: 1"]; q1 -> q0 [label = "input: b\noutput: 1"]; q2 -> q2 [label = "input: a\noutput: 1"]; q2 -> q1 [label = "...


1

False. There are infinitely many finite language. Just think of {0,1}*. This is a infinite set of finitely long strings. or say, it is union of infinite number of finite languages over {0,1} which have strings of finite length. False. Union of two non regular languages MAY BE regular but it not the case always. This answer explains it well. False. Lets have ...


1

The induction you probably want is to show that a string $w$ ends in state $q_i$ iff it satisfies the property associated to that state. The basis then is that the empty string, which must end in $q_0$, satisfies the property there. You should be more precise in some of your properties. In $q_4$, the string ends in 01 as you state, but has never seen any ...


1

Let $S$ be the list of all prefixes of words in $L$. Create a DFA with a state $q_s$ for each $s \in S$, and an additional sink state $q_\bot$. The starting state is $q_\epsilon$, and a state is accepting if it corresponds to a word in $L$. When at a non-sink state $q_s$, upon reading $\sigma$, move to $q_{s\sigma}$ if $s\sigma \in S$, and to $q_\bot$ ...


1

As the comments say, it isn't completely clear what you mean by "matching", but if you mean that for any positive integer $n$, the string $\mathtt{a}^n\mathtt{b}^n$ (that is, the string of $n$ "$\mathtt{a}$"s followed by $n$ "$\mathtt{b}$"s) is in the language, but $\mathtt{a}^n\mathtt{b}^{n-1}$ is not in the language, then what you say is correct: $L$ is ...


1

Remember that: We can view a nondeterministic computation as a directed acyclic graph of configurations indexed by time. I have a guess that in your eyes: $2^n$ for both, one directs itself and one directs others and at most every has the $\Sigma$ chance to go next state, maybe to itself, maybe the other state, so from $1$ to $n$ state, an NFA produces at ...


1

Using the accepted answer by @David Richerby -> I think what we have to do is modify the DFAs that recognize L1 and L2. Let L1 alphabet Σ1 and L2 alphabet Σ2, let Σ = Σ1 ∪ Σ2 let's say we have DFA for L1 called M, For M DFA add a extra state called y and for all the letters in Σ but not in Σ1 add a transition from all the states of M to state y. then ...


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