Recent content by Lolligirl

Oh! Could I fix it by doing this? S0 --> YS | s S --> BS | BT B --> 0 | 1 T --> SE E --> ZS Y --> i Z --> eOr maybe I'm nuts. :o

Hello everyone! Here is a question I am working on: Consider the context-free grammar G = ( { S, B, E }, { 0, 1, i, e, s }, R, S ), where R is: S --> iBSE | s B --> 0 | 1 E --> lambda | eS Convert this to Chomsky Normal Form, showing all steps. Alrighty, so I removed the lambda and got: S0...

I am not sure I understand what you mean...pick an infinite set? So you mean pick a form that isn't specific? So instead of aba and bab and adding ba to them, something like choosing aibiai and biaibi, then adding ba to those instead?. I thought we were just trying to disprove regularity for...

Okay, I think I'm getting the palindrome one now after looking over the explanation over and over. So, with the palindrome question, let's use the pairs aba and bab, which both belong to L, and add ba to them both. Then we get ababa, which still belongs to L, but babba, which does not. Thus, L...

This question is worded in a confusing way: Question: Write a Mealy finite state machine that produces the 2’s complement result of subtracting 1101 from a binary input stream (assuming at least 4 bits of input). So our input here is e.g. 10010101 or 001011 or something similar, and we want to...

The version I've seen is this: Myhill-Nerode Theorem The following are equivalent: 1. L is accepted by some DFA. 2. L is the union of some of the classes of a right invariant equivalence relation, R, of finite index. 3. The specific right invariance equivalence relation RL where x RL y iff ∀z [...

I'm sorry, but what does $\equiv_L$, and subsequently $u\equiv_L v$ if $uw\in L\iff vw\in L$ for all $w$, mean? I always get a little hung up on the notation. :B Is $\equiv_L$ "the equivalence class of L", or?

Hello everyone! :D I've been looking at the definition and proof of the Myhill-Nerode theorem for awhile now and cannot figure out what the notation is trying to tell me. Here are the languages I'm trying to apply it to, and then I'll explain what I think we're trying to do: Question: Prove...

...Oh! So that's what that notation means! I keep seeing that notation with unions and belongs to and primes everywhere, but I never really saw it used next to a picture, so I didn't understand what it was trying to say. Thank you so much for clearing that up, Evgeny; now I see how my thinking...

Okay, maybe you can help me clear something up here. My confusion starts at the bolded line (here I am relabeling the A, B, etc. letters for the original states as numbers to distinguish this DFA from the NFA on my paper; E(blah) is the epsilon closure of blah). For convenience, here's the NFA...

That...is a good point. Could I perhaps do this? https://dl.dropboxusercontent.com/u/5778771/Assignment4Number1v2.png ...But, looking at it, now there's an extra character at the end before it wraps back around to 0. I could perhaps delete my state 4 altogether and simply make state 3 wrap...

Hello again everyone! I think I have at least a decent handle on this one, but I want to check my work. Question: Convert the following NFA to an equivalent DFA (The D is going to B and the E to A on lambda). https://dl.dropboxusercontent.com/u/5778771/Assignment4GivenNFA.jpg Here is my DFA so...

Oh my goodness, that's such a good way to look at it, Evgeny! I've seen those formulae before but I didn't realize what they're used for until now. Using your and I like Serena's help, here is my divisible by 6: https://dl.dropboxusercontent.com/u/5778771/Divisibleby6.jpg And using my divisible...

Hello everyone! I'm trying to make a transition diagram for an NFA that accepts strings that are either divisible by 5 or by 6. Here's the specific question: Question: Present a transition diagram for an NFA that recognizes the set of binary strings that starts with a 1 and, when interpreted as...

Right, right, of course! That makes much more sense now; thank you very much for helping me understand, Evgeny, en hartelijk bedankt, I like Serena! :D