User James Swanson - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:23:31Z https://cs.stackexchange.com/feeds/user/99995 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/104695 1 Identifying the Equivalence Classes of a Language with equal number of 10 and 01 strings James Swanson https://cs.stackexchange.com/users/99995 2019-02-21T23:46:12Z 2019-02-22T19:27:07Z <p>I'm doing a problem where I need to find the equivalence classes of the language below:</p> <p>Let A = {x ∈ {0, 1}* | #(01, x) = #(10, x)}, where, for a, b ∈ {0, 1}*, #(ab, x) is the number of places in x where an a is immediately followed by a b.</p> <p>So I can start to see some equivalence classes. 1* and 0* both are in A, because they both have zero 10's and 01's, so the condition holds. I don't really know how I would describe the other equivalence classes?</p> <p>Any help would be great!</p> https://cs.stackexchange.com/q/104265 2 Union of infinitely many regular languages [duplicate] James Swanson https://cs.stackexchange.com/users/99995 2019-02-12T23:54:03Z 2019-02-13T04:54:17Z <div class="question-status question-originals-of-duplicate"> <p>This question already has an answer here:</p> <ul> <li> <a href="/questions/67316/infinite-intersection-union-of-regular-languages" dir="ltr">Infinite Intersection/Union of regular languages</a> <span class="question-originals-answer-count"> 2 answers </span> </li> </ul> </div> <p>I need to prove or disprove the following statement. </p> <blockquote> <p>If <span class="math-container">$A_n ⊆ \Sigma^*$</span> is regular for each <span class="math-container">$n \in \mathbb{N}$</span> then <span class="math-container">$\bigcup\limits_{n=0}^{\infty} A_n$</span> is regular. </p> </blockquote> <p>I know that if two languages are regular, then the union of the languages is also regular. I don't think that really applies to this problem, because it's the union of every <span class="math-container">$n \in \mathbb N$</span>. Also, to help with my understanding with the definitions, is <span class="math-container">$A_n$</span> a language or an alphabet, since it's a subset of <span class="math-container">$\Sigma^*$</span>?</p> https://cs.stackexchange.com/q/104215 0 Proving the singleton language {x} is regular for all x ∈ Σ* James Swanson https://cs.stackexchange.com/users/99995 2019-02-12T02:51:07Z 2019-02-12T14:45:33Z <p>So I'm aware that the singleton language is in fact regular for all x ∈ Σ*, but I do not understand why it is. A formal proof would help, but also getting some intuition as to why it is regular would also be appreciated! As of now I'm just aware of it as a property, but I don't have a good grasp on why it is regular. </p> https://cs.stackexchange.com/q/103993 1 Proving existence results James Swanson https://cs.stackexchange.com/users/99995 2019-02-07T21:05:27Z 2019-02-08T05:34:42Z <p>I'm doing a problem where I need to prove that there is a language A ⊆ {0, 1}* with both of the following properties:</p> <p>(i) For all x ∈ A, |x| ≤ 5.</p> <p>(ii) Every DFA that decides A has more than 8 states.</p> <p>To prove this, is it suffice enough to just give an example language A ⊆ {0, 1}* that holds both of these properties?</p> https://cs.stackexchange.com/q/103898 1 $A^* = B^*$ with $\{0,1\}$ contained in $A$ but not in $B$ James Swanson https://cs.stackexchange.com/users/99995 2019-02-05T17:52:19Z 2019-02-05T18:36:25Z <p>I'm trying to exhibit two formal languages <span class="math-container">$A,B ⊆ \{0,1\}^*$</span> such that <span class="math-container">$A^* = B^*$</span> and <span class="math-container">$\{0,1\}$</span> is contained in <span class="math-container">$A$</span> but not in <span class="math-container">$B$</span>.</p> <p>Finding a language for <span class="math-container">$A$</span> is very easy, but I get stuck on <span class="math-container">$B$</span>, because since <span class="math-container">$A^*=B^*$</span>, and A has <span class="math-container">$\{0,1\}$</span>, that <span class="math-container">$B^*$</span> must also have <span class="math-container">$\{0,1\}$</span>. I can't think of a language that has <span class="math-container">$\{0,1\}$</span> in <span class="math-container">$B^*$</span> but would not be in <span class="math-container">$B$</span>. Maybe I'm missing something. </p> https://cs.stackexchange.com/q/103849 1 Proof of an Infinite Binary Sequence James Swanson https://cs.stackexchange.com/users/99995 2019-02-04T21:43:25Z 2019-02-05T02:52:00Z <p>I have a problem where given an infinite binary sequence S ∈ {0, 1}∞ to be "prefix-repetitive" if there are infinitely many strings w ∈ {0, 1}* such that ww is a prefix of S.</p> <p>I need to prove that if the bits of a sequence S ∈ {0, 1}∞ are chosen by independent tosses of a fair coin, then Prob[S is prefix-repetitive] = 0</p> <p>My first instinct to tackling this problem was that the probability was 0, because of Cantor's diagonal argument, because we can construct an sequence s0 that is not in the set S. This would mean that S is countably infinite and the set of "all" possible infinite binary sequences is uncountable. </p> <p>Any help or suggestions to see if I'm on the right track to proving this problem would be great!</p> https://cs.stackexchange.com/questions/104265/union-of-infinitely-many-regular-languages/104269?cid=222900#104269 Comment by James Swanson on Union of infinitely many regular languages James Swanson https://cs.stackexchange.com/users/99995 2019-02-13T21:43:26Z 2019-02-13T21:43:26Z Ok i misinterpreted the question, so its to assume that every A(sub n) is regular, which I guess is very obvious since they would all be finite, because they are singletons. https://cs.stackexchange.com/questions/104265/union-of-infinitely-many-regular-languages/104269?cid=222881#104269 Comment by James Swanson on Union of infinitely many regular languages James Swanson https://cs.stackexchange.com/users/99995 2019-02-13T20:31:21Z 2019-02-13T20:31:21Z My only question is I thought we were assuming the language to be regular? I thought {a^n b^n} was not regular, so we aren&#39;t even starting with the assumption that An is regular. https://cs.stackexchange.com/questions/104215/proving-the-singleton-language-x-is-regular-for-all-x-%e2%88%88-%ce%a3?cid=222738 Comment by James Swanson on Proving the singleton language {x} is regular for all x ∈ Σ* James Swanson https://cs.stackexchange.com/users/99995 2019-02-12T14:21:09Z 2019-02-12T14:21:09Z I thought x ∈ Σ* isn&#39;t assuming that x is finite? Like, x could be an infinitely large string. So {x} would be a single string with infinite length. https://cs.stackexchange.com/questions/103898/a-b-with-0-1-contained-in-a-but-not-in-b?cid=222036 Comment by James Swanson on $A^* = B^*$ with $\{0,1\}$ contained in $A$ but not in $B$ James Swanson https://cs.stackexchange.com/users/99995 2019-02-05T18:33:17Z 2019-02-05T18:33:17Z Yes i meant &quot;⊆&quot; my only issue when typing the question was the symbol ⊆ with the slash in it to denote &quot;it does not contain&quot; https://cs.stackexchange.com/questions/103898/a-b-with-0-1-contained-in-a-but-not-in-b?cid=222034 Comment by James Swanson on $A^* = B^*$ with $\{0,1\}$ contained in $A$ but not in $B$ James Swanson https://cs.stackexchange.com/users/99995 2019-02-05T18:29:56Z 2019-02-05T18:29:56Z isnt {0,1} exclusively not a part of b, because it is the set {0,1} and not the string 01 https://cs.stackexchange.com/questions/103898/a-b-with-0-1-contained-in-a-but-not-in-b?cid=222032 Comment by James Swanson on $A^* = B^*$ with $\{0,1\}$ contained in $A$ but not in $B$ James Swanson https://cs.stackexchange.com/users/99995 2019-02-05T18:27:58Z 2019-02-05T18:27:58Z A={0,1} and B={0,1,00,01,10,11} would those two work?