Converting flowchart to pseudocode

[sandy.bridge]

Homework Statement

The problem I am having trouble with has to do with pseudocode and flowcharts. We were told that indeed any pseudocode can be represented by flowcharts; however, our professor said that due to the rules that he gave us for this class, it is possible to represent a flowchart that cannot be converted into pseudocode. I am having trouble seeing this, so perhaps you guys can help.

Here are the rules pertaining to the flowcharts:
atomic actions are represented by rectangular boxes. There is one arrow in and one arrow out.
Start and Stop has one arrow out and one arrow in, respectively. They are represented by oval boxes.
Diamond boxes denote choices/conditions. It says there can be one arrow in and two out (true/false).
Bullets can have one or more arrow in and one arrow out; purely presentational.

The Attempt at a Solution

I have tried numerous combinations but it seems that I am able to convert them all into pseudocode given these rules. Any ideas?

 

[jedishrfu]

The only thing I can think of is that its related to the halting problem or if an atomic operation has some sort of side-effect.

 

[sandy.bridge]

Yeah, this is the last question and it certainly has me stumped. He has yet to talk about said "halting problem" or any possible adverse side-effects exhibited by atomic actions.

I can do the opposite; that is, I could develop pseudocode that cannot be represented by the flowcharts (with his set of rules) easily. For example, if I did a pseudocode that had a choice branch that had more than two options it would require more than two arrows to leave the diamond. However, working from flowcharts to the pseudocode appears to be more difficult.

 

[rcgldr]

our professor said that due to the rules that he gave us for this class, it is possible to represent a flowchart that cannot be converted into pseudocode.

It seems that this would require an arbitrary restriction on pseudcode that wasn't applied to flowcharts in your class.

Note that there are programs like AllClear that generate flowcharts based on a psuedocode like language that the user inputs into a text file, so I'm not sure of the point your professor is trying to make.

 

[gneill]

If the pseudocode language forbids GOTO with labeled destinations, then I imagine you could lay out a flow chart with jumps into and out of overlapping loop structures that would be pretty hairy to render into pseudocode.

 

[sandy.bridge]

I'm not sure what point he is trying to make either. He explicitly points out that all flowcharts can be represented by pseudocode (opposite true as well), but he says that given the rules presented in topic 2 (which I have shared with you guys already) it is possible to build a flowchart that cannot be represented by pseudocode. I might just have to take an L on this one.

 

[jedishrfu]

I'm not sure what point he is trying to make either. He explicitly points out that all flowcharts can be represented by pseudocode (opposite true as well), but he says that given the rules presented in topic 2 (which I have shared with you guys already) it is possible to build a flowchart that cannot be represented by pseudocode. I might just have to take an L on this one.

Be creative and come up with something perhaps mix quantum entanglement into the picture or fuzzy logic. You might still get a laugh and a better grade and you just might disover what he's alluding to.

One thing I noticed is that interrupts don't seem to be included so that basically the atomic action occurs and can't be interrupted. Also what about exceptions when the atomic operation fails. These two states would require a receive interrupt arrow and transmit interrupt arrow.

 

[jedishrfu]

what if you tied the output of the if to the input of the if? How would you represent that as programmable psuedo code?

 

[sandy.bridge]

Right, that makes sense. No where in the rules does he specify rules pertaining to the different types of choice blocks that there is; hence, if you had an if block that had the true connected to very same if block, it wouldn't able to be converted to pseudocode.

What about an atomic action looped to itself? Essentially there would be no end. With pseudocode, this would have to be repetition and therefore a choice block. Does that make sense?

 

[rcgldr]

what if you tied the output of the if to the input of the if? How would you represent that as programmable psuedo code?

As a while loop

    while(interrupt_occurred == false)
    endwhile

or with a label and goto

wait_for_interrupt:
    if(interrupt_occurred == false)
        goto wait_for_interrupt

 

[gneill]

Much depends upon what control structures are available in the given pseudocode language. Are GOTOs permitted? Recursion?

 

[sandy.bridge]

There is nothing mentioned of GOTOs or recursion. This is a course in C++ and it is intended for students who have never programmed before. This is the second week of classes, and therefore, the programming language itself has barely crept its way into lectures.

 

[gneill]

There is nothing mentioned of GOTOs or recursion. This is a course in C++ and it is intended for students who have never programmed before. This is the second week of classes, and therefore, the programming language itself has barely crept its way into lectures.

The elements of the pseudo code language were not presented? How can one claim that something cannot be implemented in a language that is not specified?

 

[sandy.bridge]

Very minimal was stated about pseudocode. Here is the only information presented:
"It is quite common, in textbooks and research reports, to see algorithms written in a hybrid
of plain language and a programming language throughout Computer Science; we call these
hybrid descriptions “pseudocode” (pseudo- is a prefix that means “fake”). The idea behind
pseudo-code is to use the best of both languages. We will use plain English to describe actions
that do not need to be expressed with pin-point precision, and use programming language constructs
when the actions require precision. Do not be too concerned at this point if you don’t feel
you can tell the difference yet; it is something that comes with experience and practice.
In this course, we will focus on using language to communicate algorithms, but we’ll also
use diagrams called flow charts from time to time to help clarify our explanations."

From this description he immediately goes into applying pseudocodes to flowcharts. The question specifically states that we can answer that question based on the rules that we have for the flowcharts. It even directs me to the slide that the rules are on (which I have given).

Furthermore, for the example one can use abstract components; they need not to have meaning.

 

[gneill]

So, the flowchart rules, as given, do not place any limit on the number of STARTs?

 

[sandy.bridge]

Yeah, it does say only one of each. Thought I had that in there but I missed that. I just double checked the rest is essentially word for word:

atomic actions are represented by rectangular boxes. There is one arrow in and one arrow out.
Start and Stop has one arrow out and one arrow in, respectively. They are represented by oval boxes, and there is only one of each
Diamond boxes denote choices/conditions. It says there can be one arrow in and two out (true/false branches).
Bullets can have one or more arrow in and one arrow out; purely presentational; they have no function.

 

[rcgldr]

Bullets can have one or more arrow in and one arrow out; purely presentational; they have no function.

Bullets would be the equivalent of labels in pseudocode. Again, since some flowchart tools like AllClear use pseudocode to create flowcharts, I don't see why your professor is claiming that some flow charts don't have a pseudocode equivalent.

 

[Joffan]

Are arrows obliged to connect two elements, or can you just leave them dangling?

 

[sandy.bridge]

It doesn't say anything about that, but if there are no atomic actions/conditions left to be executed it is assumed one goes to "stop"

 

[tip_top]

Page 19 in the textbook sets out the constraints of an algorithm. It must be unambiguous, executable and terminating. Infinite loop violates this.

 

[rcgldr]

Page 19 in the textbook sets out the constraints of an algorithm. It must be unambiguous, executable and terminating. Infinite loop violates this.

True, but neither pseudocode or a flowchart has to meet these requirements, and an infinite loop could be used as an alternative to termination. With a multi-tasking OS, sometimes the "idle state" or "idle task" is an infinite loop (as opposed to a halt instruction, which may intefere with normal operation or perhaps intefere with a debugger in some environments (depending on the processor and the debugger)).

 

[sandy.bridge]

I'm going to assume tip_top is in my class. The only thing that I see on page 19 regarding flow charts is the very last sentence: a flow chart has no ambiguities, since it always uses explicit arrows to direct the flow to the next action.

 

[D H]

The problem I am having trouble with has to do with pseudocode and flowcharts. We were told that indeed any pseudocode can be represented by flowcharts; however, our professor said that due to the rules that he gave us for this class, it is possible to represent a flowchart that cannot be converted into pseudocode.

The Böhm-Jacopini theorem says that any algorithm can be implemented using only three constructs: sequence (a; b; c; ...), selection (if else), and iteration (while).

However, if you restrict how selection and iteration work there are algorithms that can be expressed via flowcharts but cannot be represented using those limited forms of selection and iteration. For example, disallow the use of auxiliary variables and you cannot express a flowchart that has an escape from multiple levels of loops¹.

Aside: Some languages provide a multi-level escape mechanism (e.g., Java), others don't (e.g., C and C++). This lack of a multi-level break in C/C++ is oftentimes one of the few allowed uses of goto.


¹ Kozen and Tseng, The Böhm–Jacopini Theorem is False, Propositionally, in Proceedings of the 9th International Conference, Mathematics of Program Construction 2008
pdf: http://ecommons.library.cornell.edu/bitstream/1813/9478/4/BohmJacopini.pdf

 

[sandy.bridge]

@DH
I took a look at that pdf. I noticed, however, for the example given that blocks 0, 1 and 2 each had 2 inputs and one of our rules for flow charts is that actions and conditions can only have one arrow in.

 

[Joffan]

@DH
I took a look at that pdf. I noticed, however, for the example given that blocks 0, 1 and 2 each had 2 inputs and one of our rules for flow charts is that actions and conditions can only have one arrow in.

If you are strict about the arrow counts, then bullets are not merely decorative; they are essential to gather inputs in such cases.

 

[sandy.bridge]

I'm not strict about arrow counts, but we are to follow the rules we were given in regards to flow chart construction. Having more than one input to actions or conditions violates the rules we were given and therefor does not address what the problem is asking.

 

[Joffan]

What I'm saying is that you can bring such a flowchart back into conformance by adding a bullet above a multiple-input box, putting all inputs to that bullet and sending the bullet output to the box of concern.

 

[sandy.bridge]

I like the way you think!

 

[D H]

@DH
I took a look at that pdf. I noticed, however, for the example given that blocks 0, 1 and 2 each had 2 inputs and one of our rules for flow charts is that actions and conditions can only have one arrow in.

Those are finite state machine transition diagrams, not flow charts. That said, it's fairly easy to convert either a Moore machine diagram or a Mealy machine diagram into a flow chart. You might get lines that cross and cannot be uncrossed -- and that's a sign of trouble for translation to a hobbled pseudocode.

 

[sandy.bridge]

Alright, let's see if I was able to capture that idea with the attached flow chart.

 

[rcgldr]

Alright, let's see if I was able to capture that idea with the attached flow chart.

As mentioned before, those "bullets" or "connectors" are the equivalent of branch target labels in pseudocode.

 

[sandy.bridge]

I don't know, then. I've tried looking online, but have not found anything. I have 2 friends in CompSci that think all flow charts can be represented by pseudo-code. I am just not seeing it.

 

[gneill]

If the rules, strictly interpreted, allow decision block outputs to feed back to their inputs, then you can create a situation where 1) there are "hidden" START points implying multithreading, and 2) create race conditions that can affect subsequent program logic.

 

[sandy.bridge]

Okay, and what happens when the conditional gets X=0 and X=1 at the same time? And in the last atomic action where you wrote "Do something clever", are you referring to me? Is this my time to shine?

 

[gneill]

Okay, and what happens when the conditional gets X=0 and X=1 at the same time?

That's the "race condition"; No telling which path will be the last one to set the variable's value.

Of course the argument against this "solution" is that there's no path to either branch from the start box, so that neither branch would be able to execute, and the branches (more correctly "tributaries"?) represent "dead code".

And in the last atomic action where you wrote "Do something clever", are you referring to me? Is this my time to shine?

Ha! Never thought about it that way... I just needed something to put in the box.