This question

File: 2017-06-16-235228_885x669_scrot.png (134KB, 885x669px) Image search: [Google]

134KB, 885x669px

>>332728
On the off chance that someone does see this and want to help out, here is the next problem set I'm working on:

File: 2017-06-15-033511_932x555_scrot.png (131KB, 932x555px) Image search: [Google]

131KB, 932x555px

>>332730
>>332728
Well, might as well post the easier stuff just to check for correctness.

>1
a) Trvial walk from a to a
b) A,D,C,B,F,E,G,J,I,H,K
c)A,D,C,A
d) A,F,G,K have odd dgree, so this graph does not have a euler circuit.
e)just drew a circuit from a,d,g,j,k,h,i,f,e,b,c,a and the other one was a mirror image of it
f)a to c
g) just drew some trees, not too difficutl
h) using both prim's algorithm and kriskels I got 56
i) using dijsktras algorithm I got 39


>2

a)this was a FSA with three nodes, where input a moves it into the next state, while B loops it for each node, the regular expression was b*ab*ab*
b) b*ab*|(.*a.*a.*b)
c) this regular expression accepts aab or a*b* (where the former is a subset of the latter. The FSA looks like two nodes, both accepted witha loop for a* on one and a loop for b* on the other
d) No idea how to do this one
b)
f)

File: 2017-06-17-000833_892x397_scrot.png (64KB, 892x397px) Image search: [Google]

64KB, 892x397px

>>332730
And lastly, this is the last snippet of the last question, #4.

Updates with questions and answers
3a) Any one to three character string that ends in 0, (0|1)(0|1)0.

3b) Similar to the first one, but with only three rows, not four, and all four nodes in the bottom row are the only accept nodes. Description: Any two-character string.

3c) Same

3d) O(|S|), since every state represents a word, out max acceptable words is equal to the number of states.

3e)idk

Everything else, however, is still up in the air so contributions are certainly welcome!

>>332737
What book is this?

>>332804
It's not a book, it's a problem set from class using Discrete Structures by Epp. What are you interested in? There's books full of problems like this if you're looking for good reads.

>>332835
You'd have got a lot more help last time if you'd posted the bit that said "I just FUCKING MADE UP the term 'FBTSA', and it isn't even a grammatical phrase".

>>332778
3e) 2^S, because the languages are defined by which nodes are accept nodes and which nodes are reject nodes. A node can be one of two possible types, and there are S nodes.

I don't know why he's abusing the term "Big-O" like this: Big-O implies you're discussing the time-complexity or space complexity of an algorithm (which this isn't), and Big-O means your assessment is asymptotic (i.e. discarding all but the most dominant term), which these answers aren't: a FSLGBTQA recognises precisely S words, at most precisely log2S long, and there can be precisely 2^S different ones.

>>332735
2 d) write out all the words you get by following all possible acyclic paths through the FSA, then alphabetise them and see if any kind of pattern strikes you. (then obviously add "and if it's <whatever> you can bung as many <whatevers> on the end as you like").

>>332888
Fuck yeah, thank you. I almost have everything now but the latter half of four, but I think in the next few hours I'll have it (I think f is just following an algorithm but G seemed difficult)

Thanks a shit ton anons

>>332903
Forgot to paste the replies to everyone else!

>>332886
Lol, yeah.. I became more serious about getting help as the deadline neared and I still wasn't able to solve these

>>332891
Goddamn thank you so much

>>332903
For 4 in general, remember that it's a "tree" in the graph theory sense (i.e. it doesn't have to have a root node or directed edges), and for 4g), have a think about where the numbers "n" and "(n-2)" might come from.

Just to update, the only remaining problems are all in 4: b, c and g

>>332908
I'm just having trouble finding the right math / model for finding the list of distinct labels. I feel like the answer is the number of vertices factorial divided by 2, just from screwing around, but I can't be certain.

bumping for any final input into 4b, c and g

>>332730
b) 0-0-0-0 and 0_8_0
You can work out the orderings, I hope.