paper 1 more qs Flashcards
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.
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?
Concealing internal details of an object, showing only what is necessary.
