Theory of Computation 2 (inc. BNF)

In computational thinking, representational abstraction is the process of

• removing unnecessary detail

• providing additional information

• enhancing and amending detail

• embellish the current detail

Data abstraction is similar in concept to functional abstraction, where ...

• the details of how the data is represented in the computer are hidden

• each piece of data is broken down into its binary equivalent

• all the bytes of data are placed in an abstract tree structure for easy retrieval

• the concept of how data is contained is philosophically approached

Composition is the opposite of decomposition, where decomposition is

• the breaking down a problem into smaller parts (sub-problems), each of which perform a specific task

• the construction of an overall blueprint of the program, including methods and functions

• the creation of the layout of pseudocode that can be converted to a composition diagram

• the adjustment of the code to enable parallel processing of what might be sequential programming statements

Problem abstraction involves removing details to represent the problem in a way it can be solved, by

• reducing down to problems that have been solved

• removing the more challenging aspects of the problem

• recalculating the more challenging algorithms until the problem does not exist

• re-calibrating the key criteria of the issue until the symptomatic criteria have been neutralised

finite state machines are useful for

• modelling and design of computer programs as well as digital hardware systems

• showing notation for context-free grammars, describing the syntax of languages

• providing tools to facilitate communication, measurement, commerce and manufacturing

• knowing the framework around technology integration

There are various symbols used in representing a Finite State Machine. They are named ...

• State, Start state, Accept state and transition

• State, Slow state, Fast state and Progression

• Start, Go state, Stop state and Halt

• Begin state, Engage state, Process and Halt

A FSM (Finite State Machine) with outputs is called a

• Mealy Machine

• Finite State Machine with Output

• Mechanical Machine

• Making Machine

Which of the following is an example of a BNF production rule?

• <digit> ::= 0|1|2|3|4|5|6|7|8|9

• R → (B → 5)

• x + y2 → 17

• x2 + 3y

What type of object is enclosed in angle brackets in Backus-Naur form?

• Definitive

• Terminal

• Non-terminal

• Special

What name is given to an object in Backus-Naur form that cannot be broken down further?

• Definitive

• Terminal

• Non-terminal

• Special