Computer Science

« first day (1483 days earlier) ← previous day next day → last day (3252 days later) »

vzn

03:30

@EvilJS most languages/ automata variations tend to fit distinctly into the chomsky hierarchy which is only a few levels deep. the use of more specific variants tends to be specialized. this is an old classic still mostly applicable.

Q: Books on automata theory for self-study

I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams.

EvilJS

03:50

@vzn By a few, you mean 4, like in C indexed from 0? Thank you, but I am familiarizing with some of them for some time now ;>

EvilJS

04:13

Last link is out.

5 hours later…

Raphael

09:21

@EvilJS You mean the community ad for chat? It would have to have an image that suggests communication (as opposed to a person doing something alone) and text to the same effect.

2 hours later…

Raphael

11:25

If anyone needs an example of a good homework question, this here is one (imho).

Q: Showing that the number of primitive-recursion programs for each function is countably-infinite

Problem Statement Prove that if a function $f$ is primitive recursive, then there are countably infinite number of primitive recursive definitions of $f$ Yes, this is a homework question. My Work I proved that there are infinite number of definitions using the following construction $$g...

computability combinatorics primitive-recursion uncountability

Valentin Tihomirov

11:54

What is the advantage of explicit message passing in parallel computing? I mean there is shared-mem multicore processor vs private memory multicomputer programming models and former is known to be simpler programmable. Why do you prefer the second?

Raphael

@ValentinTihomirov Do we? In which context? For which use cases?

That said, there simply are no real shared-memory systems around. cf NUMA.

Making communication explicit makes it easier to keep in check, analyze, and port to distributed settings.

But I don't know that you generally prefer message-passing algorithms; if you only ever run your stuff on one machine, it may create undue overhead.

Afaik, good libraries (in particular with good capsulation and abstraction) exist for both approaches.

Valentin Tihomirov

12:49

When I say that shared-memory "multicomputers are believed to be simpler to program", I do not mean that message-passing is generally preferred. What does it mean "to keep in check and analyze"?

1 hour later…

Raphael

13:56

@ValentinTihomirov 0) Avoid bugs, in particular Heisenbugs. 1) Convince yourself (and others) that the implementation is correct. 2) Make confident a-priori statements about performance.

7 hours later…

stillenat

20:40

Can someone please confirm if this is a correct state diagram for the DFA A for the language L(A) = (({0}·{1})∪{1})*. Thanks!

EvilJS

21:12

@stillenat what does {0}•{1} mean? Concatenation, so this is 01?

stillenat

@EvilJS Yes, it's concatenation.

EvilJS

(01 + 1)* ? Yes, this is ok.

stillenat

@EvilJS I think so, I'm not that good with regular expressions yet. We use set notation in our CS course.

EvilJS

@stillenat but the important part is: how did you solved it, how could you check more complicated state diagram?

stillenat

What I did was this: I rewrote the concatenation and union of sets as a single set: (({0}·{1})∪{1})*

= {01,1}*

= {ε, 01, 1,011,101,...}

and then figured out what the DFA should look like.

I'm not sure if this is the correct way of doing this

EvilJS

21:30

How would you solve (10* + 1*)*?

EvilJS

21:41

@stillenat To be sure try converting NFA to regular expression and converting DFA to regular expression, this will take the result back. This will check your result, assuming you have minimized at start.

stillenat

Thanks for the links. I'll take a look at them later. I still have a lot of homework to do.

« first day (1483 days earlier) ← previous day next day → last day (3252 days later) »

all rooms