paper 1 more qs Flashcards
(17 cards)
What is a regular language
A language that can be described by a regular expression or recognised by a finite state machine (FSM).
Why can BNF represent some languages that regular expressions cannot?
Because BNF allows recursive definitions, making it capable of representing nested or recursive structures like matching brackets.
Why are some problems considered non-computable?
Because no algorithm exists that can solve them, no matter how much time or resources are available.
List three key components of a Turing machine and their roles.
Tape: Infinite memory for storing and modifying symbols.
Read/write head: Reads from and writes to the tape, moving left or right.
Transition rules: Define how the machine changes state based on the current symbol
Give two differences between a Finite State Machine (FSM) and a Turing Machine.
A Turing Machine has infinite memory (tape); FSM does not.
A Turing Machine can modify the tape by writing; FSM cannot modify input.
What is procedural abstraction?
Hiding the specific values used and focusing on the steps (the procedure) of the computation
What is functional abstraction?
Hiding the method used to achieve a result; only the input-output behaviour matters.
To get a function
requires yet another abstraction, which
disregards the particular computation method.
This is functional abstraction.
What is the difference between procedural and functional abstraction?
Procedural abstraction hides steps; functional abstraction hides how the result is achieved.
What is data abstraction
Hiding the internal details of how data is stored; for a stack, you just use “push” and “pop” without knowing it’s implemented using an array and a pointer.
What is composition in abstraction
Combining simple procedures into more complex ones.
What are the three standard constructs in algorithms?
Sequence: steps executed one after another.
Selection: decision-making using IF/ELSE.
Iteration: repeating steps using loops like FOR or WHILE.
meaning of correctness and efficiency
Correctness: Produces the right result for all valid inputs.
Efficiency: Uses resources (time, memory) optimally.
What is information hiding?
hiding all details
of an object that do not contribute to its essential
characteristics.
Give one reason why abstract data types are important in programming.
they provide a logical description of data handling operations, allowing programmers to focus on what operations are performed rather than how they are implemented.
Describe the difference between a one-dimensional and a two-dimensional array.
Explain how a two-dimensional array could be used to store a timetable.
Q: What is the difference between a 1D and 2D array?
A: A 1D array stores data in a single row/column (like a list), while a 2D array stores data in rows and columns (like a table or grid).
Q: How can a 2D array be used to store a timetable?
A: Each row could represent a day, and each column a period. The elements store subjects or activities.
Problem abstraction/reduction
details are removed until the problem
is represented in a way that is possible to solve
because the problem reduces to one that has
already been solved
Automation
automation requires putting
models (abstraction of real world objects/
phenomena) into action to solve problems. This
is achieved by:
* creating algorithms
* implementing the algorithms in program
code (instructions)
* implementing the models in data
structures
* executing the code.
