[20:31] <@DocRamsey> Alright, its 8:30 and we seem to have a few folks here now. [20:33] <@DocRamsey> I'm going to try this out for any diagrams we may need. Please don't draw unless requested, else we'll have to ditch the idea entirely. [20:33] <@DocRamsey> http://flockdraw.com/50r2zv [20:34] <@DocRamsey> I see others there, so it seems to be doing 'something' [20:34] <@DocRamsey> If we need it, we'll use it [20:36] <@DocRamsey> So, does anybody have any questions that you'd like to start with? [20:37] Will we be proving nonregularity by identifying pairwise distinguishable languages, as discussed in the text? [20:37] *sets of strings, not languages [20:38] <@DocRamsey> Distinguisability can be a powerful feature. But no. [20:39] <@DocRamsey> For now, you prove something is not regular through closure or the pumping lemma. [20:39] <@DocRamsey> If the question does not explicitly state which to use, you may use either. [20:40] I imagine it is very likely we will be seeing similar problems to the ones from the quizzes? [20:41] <@DocRamsey> Some will be similar. Some will be different. They are a good beginning study tool though either way. [20:42] how do you determine non regularity with the pumping lemma [20:42] <@DocRamsey> The general idea is that you assume the language is regular. [20:42] <@DocRamsey> Then show it doesn't obey the pumping lemma. [20:42] <@DocRamsey> Which is a proof by contradiction. [20:43] <@DocRamsey> Because if the language WAS regular, it would have obeyed the pumping lemma to start with. [20:43] What is the pumping length, or "the first P symbols"? [20:44] which means that at least one portion of the language can be repeated to generate more strings in the language? [20:44] <@DocRamsey> It is the length at which a machine must loop. At worst, p is the number of states in a machine that recognizes a language. [20:44] <@DocRamsey> ^ this was to Ian. [20:45] <@DocRamsey> To MichaelD : I'm unsure what you mean here. The pumping lemma really only matters for infinite languages. For finite languages, they are always regular. An infinite language may be regular or non regular. If it is regular, it will have some part in it which you can loop to get another string in the language. [20:45] Will we be intersecting regular languages using RE or is it only possible with an FA? [20:45] <@DocRamsey> MichaelD: To prove something is not regular, you show that no matter what you 'try' to loop on, you can't find something suitable in a certain string that you pick in the original language. [20:46] <@DocRamsey> nsnow: They are equivalent. You can intersect any regular languages no matter their expression because oyu can always convert to the most convenient expression of the language. [20:47] <@DocRamsey> Q/A may be getting muddled some. So let me go in order. [20:47] <@DocRamsey> MichaelD: did we finish your answer? [20:47] <@DocRamsey> MichaelD: or rather your question? [20:48] <@DocRamsey> Alright, well moving on. EchoLynx - did we finish your question? [20:48] Yes you did [20:48] <@DocRamsey> MichaelD: okay great! [20:48] <@DocRamsey> EchoLynx: ? [20:48] Yes. But I have a little more. [20:48] <@DocRamsey> Related or unrelated? [20:48] Related. [20:49] <@DocRamsey> Okay, let's push on there for a second. Ask your follow up. [20:49] How can you determine the maximum number of states in a machine that accepts a language. [20:49] Because that size, plus one, is the pumping length - right? [20:49] *at worst* [20:49] <@DocRamsey> at worst it is 'that size' [20:50] <@DocRamsey> If the language is regular, you can just write a DFA for it and then determine p. [20:50] <@DocRamsey> because p = # of states at worst [20:50] That answers my question. Thank you. [20:50] <@DocRamsey> If the language is non-regular, you can only talk about p abstractly. It doesn't exist in reality. It only exists long enough to use as a construct for the proof by contradiction in the pumping lemma. [20:51] <@DocRamsey> Alright! [20:51] <@DocRamsey> nsnow: Do we complete your question? [20:51] <@DocRamsey> Did* [20:52] Yes, I think so [20:52] <@DocRamsey> Alright so we're caught up. [20:53] <@DocRamsey> Any other follow up questions related to one of those three lines of questioning? [20:54] Should we expect to know how to use the pumping lemma and closure properties in one proof? [20:55] <@DocRamsey> I'll do my best to remove the two from one another. But, if you happen to see a closure property that doesn't match the assumptions I give you, then you'd be leaving something unproven or as an assumption at the end. [20:55] I think I understand intersecting on regular expressions but how do you intersect on an FA [20:56] When proving nonregularity using closure, how do we pick a good language to perform an operation with (such as intersection)? Should we memorize some nonregular languages so we have some goals to work towards? [20:56] I'm the opposite, could you explain both? [20:57] <@DocRamsey> Using the construction proof we did in class involving the cartesian product. If machine 1 has states {a,b} and machine 2 has states {c,d}, you'll make a new machine with states { (a,c), (a,d), (b,c), (b,d) } where the first state comes from the first machine and the second state from the second. Then, doing something similar to the set construction when we converted nfa to dfa, you can invent the new machine that is the intersection of both. Th [20:58] <@DocRamsey> Okay, let me take these instructions one at a time. MichaelD - do you remember doing this? [20:59] Didn't that consist of switching which states accept and ones that don't? [20:59] I think I was absent for that proof. [20:59] Reversing the accept and non accept states? [20:59] <@DocRamsey> MichaelD: get notes! [21:00] <@DocRamsey> nsnow: no, the accept states in the new machine are only the states which are accept states in both of the first two machines. [21:00] <@DocRamsey> So if a and d were accept states, then in the new machine only the state (a,d) is an accept state. [21:00] Ahhh, I remember that [21:00] I was thinking of inverse [21:01] <@DocRamsey> Complement of a regular language can be done by changing all accept states with all non accept states and vice versa on a DFA. [21:01] <@DocRamsey> EchoLynx: this is a tough question! [21:01] <@DocRamsey> The Kleene operators are not good choices for the operation. [21:02] <@DocRamsey> Intersection is most often used. [21:02] <@DocRamsey> You should be able to look at many languages and realize they are non regular. The list on the website for that homework is a good start. [21:03] <@DocRamsey> Anything that involves actually counting infinitely (and not just modulating a counting value or toggling one through a few 'states') [21:03] <@DocRamsey> Sometimes identifying that is difficult, which makes it a challenge, but often it is straight forward. [21:04] So, to rephrase, anything that requires remembering a variable number is a good heuristic? [21:04] <@DocRamsey> As long as that number has no bound [21:04] <@DocRamsey> For example: [21:04] <@DocRamsey> 0^n 1^n is a popular language we know as non regular right? [21:04] Correct. [21:04] <@DocRamsey> well that's if n >= 0 [21:04] <@DocRamsey> it is also non regular if n >= 100 [21:04] <@DocRamsey> but if you say n < 10000000 [21:04] Then it's regular. [21:05] <@DocRamsey> There is a bound on n - it is regular. [21:05] <@DocRamsey> Why is it regular? [21:05] We can draw a (very large) FA to represent it. [21:05] <@DocRamsey> Yup. The language becomes finite actually. [21:05] <@DocRamsey> n < 10 is easier to understand I suppose [21:05] <@DocRamsey> You can list all the strings [21:06] <@DocRamsey> 01 0011 000111 00001111 0000011111 .... 00000000001111111111 [21:06] <@DocRamsey> and the empty string [21:06] <@DocRamsey> So you can definitely draw the nfa for it [21:06] <@DocRamsey> even if it would be annoying. [21:06] So a better heuristic is thinking about whether or not it's possible to write all the strings. [21:06] <@DocRamsey> Counting Infinitely. [21:06] *accepted strings [21:07] <@DocRamsey> 0*1* has infinitely many accepted strings and is regular. [21:07] <@DocRamsey> even 0* [21:07] <@DocRamsey> It is about having to count infinitely only. [21:07] <@DocRamsey> Keeping track of an ever growing number of things that has no upper bound. [21:07] <@DocRamsey> You run out of state space to do that eventually. [21:08] Ok, that helps a bunch. Thank you. [21:08] so 0* is regular even though it is infinite because there is no "counting"? [21:09] <@DocRamsey> Yes, you don't have to think about what you've done before at all to figure out if you accept at any point in the string. [21:09] <@DocRamsey> All you would have to know is that the next symbol is a 0 and nothing else. [21:09] <@DocRamsey> If it ever isn't, reject forever. [21:09] <@DocRamsey> This is how state works. [21:09] <@DocRamsey> Where you are may depend on the past, but only in a modulating way and never in an infinitely counting way. [21:09] <@DocRamsey> This is why we can do things like 'divisible by x' [21:09] <@DocRamsey> Or 'even/odd' [21:10] <@DocRamsey> But this is why we can't do things like, same number of a's as there are b's [21:10] <@DocRamsey> I'd have to count all the a's...and there could be more a's than there are states in any machine that can ever be created [21:14] <@DocRamsey> Does anybody have any lingering questions? [21:14] <@DocRamsey> Is there anything I can make more clear? [21:16] We need to make sure we explain everything in our proofs... uh... what else... [21:17] Can you review 4.2a from the book? [21:17] <@DocRamsey> Show your work if you want partial credit for some of it. [21:17] <@DocRamsey> I don't have my book with me (didn't think 100% of the snow day when I left), but I have the author's solution manual [21:18] <@DocRamsey> Give me one second and see if I can figure it out from there. [21:18] I have it, one moment. [21:18] If L1 is a subset of L2 and L2 is regular, then L1 can be regular or nonregular. Why? [21:18] Correction: not why, give an examply of why. [21:19] <@DocRamsey> Well, let's say L2 is 'all strings' [21:19] <@DocRamsey> That's a regular language right? [21:19] Yep. [21:19] <@DocRamsey> So give me a regular expression. [21:20] Can I draw a DFA? [21:20] <@DocRamsey> You could. Give me an english description of a regular language instead. [21:20] (1+0)* [21:21] <@DocRamsey> That would work Joe. Give me a DIFFERENT regular expression that doesn't describe L2. [21:21] <@DocRamsey> Or just describe some other regular language in English. [21:22] 10* [21:22] hello [21:22] <@DocRamsey> is that a subset of the language of all strings? [21:22] Yes. [21:23] <@DocRamsey> Okay so you've shown half of the answer. [21:23] <@DocRamsey> Now, give me any non-regular language description. [21:23] 0^n 1^n while n>=0 [21:23] <@DocRamsey> is that a subset of the language of all strings? [21:23] Yep. [21:24] Ok, thank you. [21:24] <@DocRamsey> What we've proven is that the subset as an operator is not closed for regular languages. [21:24] <@DocRamsey> Just because A is a subset of B and B is regular...it proves nothing about A at all. [21:24] <@DocRamsey> The key I think is realizing that L2 can be the language of all strings. [21:25] <@DocRamsey> Because the problem solves itself at that point. [21:25] <@DocRamsey> But even if you choose L2 as 0*1* [21:25] <@DocRamsey> then you can choose your string Lynx to show the second part [21:25] <@DocRamsey> and you could choose 0* to show the first part. [21:26] Thank you. That helps a lot. [21:26] <@DocRamsey> Great! Welcome DrewBeardmore [21:27] <@DocRamsey> Almost closing in on one hour and thus I'm starting to turn into a pumpkin. Are there any last minute questions out there? [21:27] pumpkin? lol [21:28] On the exam, should we follow any kind of formal proofing methods? [21:28] The quiz is sorta informal [21:28] I'm going to sign off for the night ladies and gentelman, but I will be studying near the closest white board to the classroom starting around 10:00 maybe earlier. Everyone is welcome to join me. [21:28] <@DocRamsey> We use contradiction for the pumping lemma and closure. [21:28] Good night [21:29] <@DocRamsey> Otherwise, always state your assumptions and clearly describe what you're doing. [21:29] Sounds good, gnight [21:29] okay sounds good [21:29] <@DocRamsey> If I say something like "prove this language is regular" You should clearly write why what you did proves this. [21:29] <@DocRamsey> For example, I drew a DFA for this language and therefore I know it is regular. [21:30] okay [21:30] <@DocRamsey> For the pumping lemma, you need to state your assumptions and explain why you're doing some of the things you're doing. You may assume the reader (me) knows the pumping lemma, but you may not assume that I know what assumptions you're making when you write your proof. [21:30] <@DocRamsey> This is a mistake that many folks lost a couple points for on the quizzes. [21:31] <@DocRamsey> Good question DrewBeardmore. Did I answer it sufficiently? [21:31] Do any other mistakes you observed on the quizzes stand out in your memory? [21:32] <@DocRamsey> Most folks couldn't do rips and tried to just write an RE. Most failed. [21:32] <@DocRamsey> The REs were close, but almost always wrong. [21:32] <@DocRamsey> In the first quiz I asked for a DFA and some drew an NFA. [21:32] Okay [21:32] i mean yes [21:33] haha [21:33] <@DocRamsey> Good! [21:33] <@DocRamsey> EchoLynx: Those stand out the most I think. [21:33] <@DocRamsey> Of course, I didn't actually see quiz 4, but I imagine it was a hard one.