# Exercise 03 Question 03 - FDD to ZDD

+1 vote

Hello,

In the third question, the FDD was

where the first part was to get RMNF from FDD, for which I solved it as

(c&b)^b^a^true

which was accepted in the online exercise system

the next part: What is the set representation of the ZDD for it?

I solved it as following.

and my set representation answer {{a,b};{b,c};{c};{}} wasn't accepted. Can you please help me out where I am missing out or making mistake? I also verified my answer with online tool.

I'm really impressed! The answer you mentioned {{a,b};{b,c};{c};{}} is completely correct. So is the way you computed it. Also, you documented it well, used the teaching tools correctly, and precisely showed the result from the teaching tools.

However, unlike you said, you never submitted {{a,b};{b,c};{c};{}}. You submitted some wrong answers, and {{a,b},{b,c},{c},{}} as shown by the teaching tools. Do you spot the difference? The solution you mentioned uses semicolon in the outer set, the solution you submitted uses comma all the way.

You might be curious why our teaching tools show the mathematical syntax (comma all the way), and our online exercise system insists on two different separators. On one hand, that prevents careless copy-paste. On the other hand, parsing gets easier.

Side-note on parsing: If we allowed nested sets of arbitrary depth with one fixed separator, we'd parse a context-free, non-regular language. Since we have a fixed depth of two, we have to options to parse that regularly. With two different separator (one per depth-level), we can split by the outer separator (in linear time), and split the resulting elements again by the inner separator. (Then just throwing away { and }, trimming off some white spaces, and handling empty strings) If we have only one separator, we can also split by this separator (in linear time). But we then get one flat list of elements like “{{a” and “b}” and “{c” and so on. In order to turn it to a list of list, we'd parse every element in order and keep track in which depth-level we are. Luckily, we already know that there are only two levels. Hence, we can just use a boolean variable to track whether we are in an inner or in the outer set. If the depth wasn't fixed, we'd need to count the depth we are parsing. This doesn't sound spectacular but it is. That's the difference between regular, and non-regular, context-free parsing! I'm digressing. So yes, we could also parse it in linear time with just one separator but it would be a bit harder to implement – especially since we have all weapons of programming at hand. The variant with two separators is then just a split by the outer separator, and a map of a split by the inner separator in the result of the first split. (Plus some trimming, and filtering)

by (25.6k points)
selected by