Logic - 2017-04-06

« first day (232 days earlier) ← previous day next day → last day (2879 days later) »

Xin Yin

09:54

Can someone help me write an MSO formula to capture this.
The words in the language are formed using 0s and 1s . At every position, number of 1s in the prefix is greater than or equal to the number of 0s . For Example, 1100 is a valid word but 1001 is not.
I also need to encode the fact that the string has equal number of 1s and 0s.

user21820

10:07

@XinYin: I see you've already asked an equivalent question on the main site. But have you read the FAQ including the linked How-to-ask page?

Xin Yin

I am sorry if I made a mistake

I am new here

user21820

On Math SE, we do not like questions that have no context (where does the question come from, why do you want an answer, and what you have tried). That's all.

The official reason is that we can give a better answer if this information is provided.

My personal reason is that I want to see effort first.

Xin Yin

I tried writing a DFA for the statement but I couldn't

user21820

Do you know that regular languages are exactly the languages captured by DFAs?

Xin Yin

I wanted to know if it is actually possible to express it in MSO

Yes

I do know that they are equivalent

user21820

10:11

Oh wait; I misinterpreted the answer you got there.

I'll need to think about your question first, but if the answer there is correct then it's hinting that you can't do it.

Which would require you proving that the set you want is not regular.

Xin Yin

This is actually a question from a quiz I gave yesterday. We haven't covered proving a set is non-regular yet in our course

Is there a way similar to the EF games technique ?

user21820

Hmm.

I'm not familiar with using the EF game technique. One common way to prove some language not regular is the pumping lemma.

Xin Yin

I'll look into it. Thanks a lot !

user21820

@XinYin: If a language L is regular then there is a DFA for it with finitely many states, so if you pick a string in L that is long enough then it must traverse a loop.

That loop can be pumped, meaning that duplicating that loop arbitrarily many times still yields strings in L.

From that you try to obtain a contradiction.

Xin Yin

I had a similar idea but I didn't know about the pumping lemma. I'll need to look at it. Thanks for the help

user21820

10:25

Sure.

You're welcome!

3 hours later…

user21820

13:18

@shredalert: Just to let you know, I've just taken a look at Henle's website but one of his articles is logically flawed. It is a follow-up from this part I'll give you more details if you wish, but the basic flaw is that you cannot use any circular definition, so the theorem in the book and the claim on the website are simply invalid.

If it's not clear why circular definitions cannot be permitted, consider the following 'definition' of "strange": Call an integer strange if and only if all smaller integers are not strange. I'll leave it as an exercise for you to deduce a contradiction from this definition alone.

1 hour later…

shredalert

14:31

@user21820 will note that if I never use that resource.

@user21820 I just spent about an hour pulling my hair out trying to construct a not gate from $\neg (P \vee Q)$ gates

Had to figure out the gate in the book was a not P or Q gate then worked backwards

did it with 4 of them

shredalert

14:50

nvm, found an error in that lol

shredalert

15:08

fixed it, but needed to use 5 gates

user21820

15:27

@shredalert That base gate is also called a NOR gate, and is universal, meaning that every possible boolean function can be built using NOR gates. This fact was actually used in one of the early Apollo space probes! Another universal gate is the NAND gate.

However that was in old times where the gates were actually rather big. Modern processors use CMOS gates where it is actually more efficient to have separate NOT, AND and OR gates and so on than to use NAND gates everywhere. Just a bit of trivia for you! =)

But why do you need so many gates to construct a NOT gate?

NOT(x) = NOR(x,x) = NAND(x,x).

Am I mis-interpreting your statement?

@shredalert: If you're referring to my old challenge of constructing an XOR gate, then yes the direct translation takes 5 NAND gates or 5 NOR gates, but there's a clever circuit that only uses 4 NAND gates and for some curious reason the same circuit with all the gates replaced by NOR gates also works!

@shredalert: Oops sorry I remembered wrong! The 'curiosity' gives an XNOR gate, not a XOR gate. If you give up for XOR using 4 NAND gates, the solution can be found on Wikipedia.

I'm going to sleep soon. So see you around next time! =)

5 hours later…

shredalert

20:27

@user21820 Have a good night. I was talking about another puzzle. Using NOR gates to construct a Not gate. I managed to do it with 5.

« first day (232 days earlier) ← previous day next day → last day (2879 days later) »

all rooms