dolio 2017-03-02 15:45:29
I don't think RE is.
Welkin 2017-03-02 15:45:47
lambdabot: @messages
lambdabot 2017-03-02 15:45:47
You don't have any messages
Welkin 2017-03-02 15:45:51
D:<
ski 2017-03-02 15:46:47
@tell Welkin You've got a message
lambdabot 2017-03-02 15:46:47
Consider it noted.
dolio 2017-03-02 15:46:53
Recursive is.
Nolrai 2017-03-02 15:47:26
So in 8.0.2 deriving Typable is unnessary?
Nolrai 2017-03-02 15:47:42
*ghc 8.0.2
lyxia 2017-03-02 15:50:06
it has been unnecessary for a while.
Nolrai 2017-03-02 15:50:40
Really?
Nolrai 2017-03-02 15:50:47
I am behind the times.
mniip 2017-03-02 15:58:21
dolio, wait
mniip 2017-03-02 15:58:33
which is the class for which a TM terminates and says yes/no
monochrom 2017-03-02 15:58:56
Recursive.
mniip 2017-03-02 15:59:12
aha
monochrom 2017-03-02 15:59:36
Recursively enumerable = semidecidable = If the answer should be yes, the TM terminates and says yes; else the TM could say no or go on forever
mniip 2017-03-02 15:59:47
RE are the ones for which a TM terminates or doesn't
mniip 2017-03-02 15:59:48
right
Nolrai 2017-03-02 16:02:21
And Regular = decided by a context-free grammar, right?
mniip 2017-03-02 16:03:08
cfgs are strictly weaker
monochrom 2017-03-02 16:03:09
regular expression, finite state automaton
mniip 2017-03-02 16:03:19
ah er
mniip 2017-03-02 16:03:20
regular
monochrom 2017-03-02 16:03:28
context-free is when nondeterministic pushdown automaton
mniip 2017-03-02 16:03:30
cfgs are strictly stronger than regulars
mniip 2017-03-02 16:04:20
and contextful grammars are linearly bounded terminating TMs iirc
monochrom 2017-03-02 16:04:31
(In the case of finite state automata, determinism and nondeterminism don't matter, apart from exponential blowup.)
mniip 2017-03-02 16:04:48
yep
mniip 2017-03-02 16:04:57
deterministic pushdown automata define DCFGs
mniip 2017-03-02 16:05:07
which is strictly weaker than CFGs
monochrom 2017-03-02 16:05:12
Strangely, by the time you hit TM, again det vs nondet don't matter.
mniip 2017-03-02 16:05:38
are you sure in the case of a linearly bounded TM?
monochrom 2017-03-02 16:06:16
No.
monochrom 2017-03-02 16:06:32
I just meant unrestricted TM.
mniip 2017-03-02 16:06:36
ok
monochrom 2017-03-02 16:06:47
Haven't studied the context-sensitive class.
mniip 2017-03-02 16:07:23
we have barely touched it in our language theory course
monochrom 2017-03-02 16:07:30
It does seem a less popular topic.
Nolrai 2017-03-02 16:07:42
Because you can simulate NDTM's fairly straightforwardly with a DTM.
Nolrai 2017-03-02 16:09:05
Are infinite Regular Expressions equivalent to CFGs?
monochrom 2017-03-02 16:09:18
What are those?! :S
dolio 2017-03-02 16:11:03
Any language can be given an "infinite regular expression".
mniip 2017-03-02 16:11:21
do you mean a countable state automaton?
mniip 2017-03-02 16:11:34
:p
Nolrai 2017-03-02 16:11:37
mniip: I think so?
dolio 2017-03-02 16:11:39
Just take the union of all the strings in the language.
mniip 2017-03-02 16:11:43
well
mniip 2017-03-02 16:11:47
that's an unrestricted language
mniip 2017-03-02 16:12:10
because it all depends on the final states set
Nolrai 2017-03-02 16:12:16
Right.
mniip 2017-03-02 16:13:03
if you however restrict to recursively enumerable or computable sets, you get RE and resp. recursive languages
dolio 2017-03-02 16:13:09
Or yeah. Define states for every possible string, and circle the ones in the language.
Nolrai 2017-03-02 16:13:50
I meant things like mp='('mp*')' .
mniip 2017-03-02 16:16:24
like an EBNF?
mniip 2017-03-02 16:16:29
that's just a fancy cfg
monochrom 2017-03-02 16:17:03
Yes it doesn't exceed CFG yet. It's just using syntax sugar.
monochrom 2017-03-02 16:17:18
(FSVO "yes" I guess)
