cs paper 1 Flashcards
regular expresssions
- a tool which allows computers to work with text patterns
- used for:
Validation of input
match patterns in text files
Metacharacters
- (astrix)= 0 or more preceding elements
+ = 1 or more preceding elements
? = 0 or 1 preceding elements
() = used to grp toghther regular expression
- (astrix)= 0 or more preceding elements
= OR operator
Syntax
- all programms must follow strict rules regarding their structure
BNF
- 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
parsing
- working out if a given statement is valid according to the given BNF production rules
syntax diagram
- graphical representation of BNF
time/space complexity
-no. of steps/memory used by an algorithm
Big O notation
complexity of algorithms -tips
hardware limits
-problem requires more computer memory than is feasible
-problem has an exponential complexity = using more processors makes little difference
tractable problems
Any problem, which is solvable in polynomial time or better
intractable problem
Any problem which cannot be solved in Polynomial time or better
computable problem
If an algorithm can be constructed to solve a particular problem then that problem is computable
problems computer can’t do/easily
-borad, poorly defined problems
-problems that call for subjective evaluations
halting problem
-Shows that there exists some problem which simply cannot be solved by computers
turing machine
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.
transition function
importance of universal turing machine
-anything a turing machine can compute a computer can
-provides def of what is computable
-genral purpose machine
universal turing machine
-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
