cs paper 1

Question 1

regular expresssions

Answer 1

• a tool which allows computers to work with text patterns
• used for:
  Validation of input
  match patterns in text files

Question 2

Metacharacters

Answer 2

• • (astrix)= 0 or more preceding elements
    + = 1 or more preceding elements
    ? = 0 or 1 preceding elements
    () = used to grp toghther regular expression

= OR operator

Question 3

Syntax

Answer 3

• all programms must follow strict rules regarding their structure

Question 4

BNF

Answer 4

• formal mathematical way of defining syntax unambiguosly
• consists of:
  set of terminal symbols
  set of non-terminal symbols
  set of production rules

<LETTER> ::=A|B|C....|Z
</LETTER>

= OR

Question 5

parsing

Answer 5

• working out if a given statement is valid according to the given BNF production rules

Question 6

syntax diagram

Answer 6

• graphical representation of BNF

Question 7

time/space complexity

Answer 7

-no. of steps/memory used by an algorithm

Question 8

Big O notation

Question 9

complexity of algorithms -tips

Question 10

hardware limits

Answer 10

-problem requires more computer memory than is feasible
-problem has an exponential complexity = using more processors makes little difference

Question 11

tractable problems

Answer 11

Any problem, which is solvable in polynomial time or better

Question 12

intractable problem

Answer 12

Any problem which cannot be solved in Polynomial time or better

Question 13

computable problem

Answer 13

If an algorithm can be constructed to solve a particular problem then that problem is computable

Question 14

problems computer can’t do/easily

Answer 14

-borad, poorly defined problems
-problems that call for subjective evaluations

Question 15

halting problem

Answer 15

-Shows that there exists some problem which simply cannot be solved by computers

Question 16

turing machine

Answer 16

formal model of computation that
consists of a finite state machine , a read/write head and a tape that is infinitely long in one direction.

Question 17

transition function

Question 18

importance of universal turing machine

Answer 18

-anything a turing machine can compute a computer can
-provides def of what is computable
-genral purpose machine

Question 19

universal turing machine

Answer 19

-capable of representing any FSM
-description of FSM to be used is read off same tape as input data and used to process the input data as usual
-act as interpreters,due to the way they read their instructions in sequence before executing operations on input data