Language theory help

File: arturia12.jpg (379KB, 2244x1654px) Image search: [Google]

379KB, 2244x1654px

Please?

File: the daily grind2.jpg (203KB, 1024x1298px) Image search: [Google]

203KB, 1024x1298px

Ill paypal anyone $15 for an answer

>>60878353
I understood what you were saying until you got to L <m L'

What does that notation mean? Also, what do you mean by a language complement? If A = {0} does A' = {1,B} over a binary alphabet? Just a little confused by all the terms

>>60878804
Sorry, L <=m L' is the notation for mapping reducibility, I can't type it out nice because I dont think theres typesetting format here like /sci/.

Given a language L = {0} (contains the single element zero), the complement of this language, denoted L' would imply it contains all things that are not L, thus being L' = {00, 01, 1, 1101010, anything you can think of that isn't 0} i.e an infinite set (Assume were talking over a binary alphabet)

>>60878888
So the question is whether everything in A' is reducable to 0?

>>60878758
I can answer but you have to some services for me first

>>60878907
Im not 100% sure the converse holds, but the question is asking is L mapping reducible to L' (Is any decidable language reducible to its complement)

>>60878939
What you want

>>60878949
You have to give me that hot bubble butt of yours

File: 1490232657148.png (51KB, 728x354px) Image search: [Google]

51KB, 728x354px

>>60878888
Ok so I just looked up some definitions. A is the alphabet {0} and it is a subset of (0|1|B)*. A' is an alphabet that is also a subset of the same thing. According to this picture, since A and A' are both subsets of the same sigma ((0|1|B)*), then there needs to be a computable (bijective ?) function f that maps from A to B. If such a function existed, A and A' would be isomorphic, and if they're isomorphic they would have the same cardinality. Unfortunately A has a cardinality of 1 and A' has a cardinality of infinity. I don't think it's true, but I'm also really new to all this stuff

>>60878974
oops I wrote B but I meant A'

>>60878974
Im getting really confused now, just to confirm, the "if and only iff or "iff" " means that if theres an element x in A, then theres an element f(x) in B, Similarly, if theres an element in B then there must be some element y in A that gives f(y) which was the element in B. Does this sound right? Im questioning my foundation of everything right now

>>60879028
Yes that's exactly right.

So you couldn't just assign f(x) = 1. Sure, for all x in A ({0}), f(x) is in A'. But, you can pick several things in A' where there is no element x in A so that f(x) = that thing.

>>60879048
Yes this was my reasoning, apparently it is not correct.

I actually happened to stumble upon the answer to this question but I dont even agree with the logic. http://cseweb.ucsd.edu/classes/wi00/cse105/hw5sol.pdf go to problem 4(b)

I understand most of it, but I cant see how this disproves my claim. So confused as to why what im saying is wrong

>>60878353
you should (also) ask in /sci/ it might be a better place than here. :^)
if I wasn't in bed already i would try to answer but good luck!

>>60878353

(disclaimer, been a LONG while since I took a formal language class. This might be complete nonsense. Don't blame me if you use this answer and get this wrong on your homework. Sorry your prof is being an asshat and you have to ask /g/ for homework help. I suggest you try some IRC channels instead.)

A language is turing decidable if and only if there exists a turing machine that accepts on some language L and rejects on anything not in L.

Note that there is a meaningful distinction between a rejection state and not halting. If we say that a language is turing decidable, it means necessarily that this will reach a rejection or acceptance state.

So with the question in the pic on the OP, we know that we have a turing decidable language A, and that there exists a turing machine that will tell us, definitively, if an input is in A, and if it is not in A.

Therefore, the answer is true. It doesn't matter that A' is an infinite set, it will simply enter an accepting state as soon as it is certain that it hasn't seen something in A, the same way that the TM for A will enter a rejection state as soon as it is certain it hasn't seen something in A.

>>60879111
So it looks like they defined f as a turing machine such that f(0) = 1 (just an example, w2 in their work) and f(anything else) = 0. That would work. I guess it doesn't have to be bijective

>>60879140
disregard this, saw your link to that ucsd homework, I'm wrong.

https://en.wikipedia.org/wiki/Rice%27s_theorem

>>60879144
So in other words this procedure is done to construct L', we don't actually start off with it? That doesnt make much sense, if we start off with a Language we already know its complement, so the problem should be whether or not we can construct the function that maps elements from L to L'.

I had assumed that its impossible to construct the function because something like 101 which is in L' wouldn't be possible to be mapped to, not even sure if I understand properly

>>60879272
Yes Ive read it at least 10 times over, what theyre doing doesnt prove anything, as they put it, no matter what "w" you simulate on the tm you will never get something other than the result of f(0) since theres only one thing in L. Its impossible to ever get elements such as 01, 101,1010101010, 0100000, or whatever which are all in L'.

Anyone understand this well?