AQA A2 Computing - 1.6 Regular Expressions, BNF and RPN

Question 1

Natural Language

Answer 1

Comprises of a set of rules and governed by rules which define the order in which words may be put together to craete speech. These rules define the grammar or syntax of the language.

Question 2

Formal Language

Answer 2

Defined using two components: its alphabet and its rules of syntax. For example, a formal language is used to describe the hardness of lead in pencils.

Question 3

Regular Language

Answer 3

Any language that a Finite State Machine will accept.

Question 4

Metalanguage

Answer 4

A metalaguage is a language used to describe a real language.

Question 5

Real Language

Answer 5

A real language is consists of strings of characters chosen from some set or alphabet of characters.

Question 6

Regular Expression

Answer 6

A notation for defining all the valid strings of a formal language or a special text string for describing a search pattern.

Question 7

Regular Expressions: Alternation (bed?ban)

Answer 7

A vertical bar ? is used to separate alternatives. For example bed?ban is used to match strings bed and ban.

Question 8

Regular Expressions: Character Class (b[ae]d)

Answer 8

An alternative way of representing alternation. B[ae]d matched bad and bed because [] encloses a list of alternative characters. Particularly useful for ranges of characters. E.g. [a-z] for all lower case characters, or [A-Za-z] for all upper and lowercase characters.

Question 9

Regular Expressions: Grouping (gr(a?e)y)

Answer 9

Round brackets are used to define the scope and prescedence of the operators, among other uses. E.g. gray?grey and gr(a?e)y are equivalent patterns describing the set containing grey and gray.

Question 10

Regular Expressions: Negation (n^t)

Answer 10

This will match any character that is not in the character class. N.B This does NOT meat ‘an n not followed by a t’. It means ‘an n followed by a character that is not a t’

Question 11

Regular Expressions: Quatification “?”

Answer 11

Indicates that there is zero or one of the preceeding element. E.g. colou?r matches color and colour

Question 12

Regular Expressions: Quatification “*”

Answer 12

Indicates that there are zero or more of the preceeding element. E.g. ab*c matches ac, abc, abbc, abbbc and so on

Question 13

Regular Expressions: Quatification “+”

Answer 13

Indicates that there are zero or more of the preceeding element. E.g. ab+c matches abc, abbc, abbbc and so on but NOT ac

Question 14

Backus-Naur form (BNF)

Answer 14

a notation for expressing the rules for constructing valid strings in a regular language

Question 15

Syntax

Answer 15

The rules by which words and symbols are combined to form language structures (expressions, statements etc.)

Question 16

Recursive Definition

Answer 16

“A recursive definition is a recursive defininition!” One that is defined in terms of itself.