Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

COMP11212 - Computation > Part 1 Glossary > Flashcards

Part 1 Glossary Flashcards

1
Q

Algorithm 1

A

Turns an NFA into a DFA

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Algorithm 2

A

Turns an automaton into a pattern

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Algorithm 3

A

Takes a pattern and turns it into an NFA with e transitions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Alphabet

A

A set of letters

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Ambiguity

A

A word is ambiguously generated if we have a grammar that has two parse trees for it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Backus-Naur form

A

A particular way of writing down a grammar popular within computer science, in particular for the syntax of programming lanugages

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

CFG

A

Context free grammar. Rules for generating words using rewrite rules

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Context free

A

A language is context free if there is a CFG generating it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

NFA

A

Non deterministic finite automation. Defines a language

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Non terminal symbol

A

An auxiliary symbol used to describe a grammar- we want to create words that do not contain auxiliary symbols

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Parse Tree

A

A parse tree shows how a string can be generated from a given grammar in a more useful way then a derivation.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Pattern

A

A particular kind of string used to define lanugages

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Regular

A

A language is regular if it can be defined using a pattern

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Regular expression

A

A pattern

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Right-linear

A

A grammar is right-linear if its production rules are particularly simple. Non terminal symbol always appears on the right side

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Simulation

A

A special relation between the states of two automaton. Its existence implies that the language accepted by the first automaton is a subset of that accepted by the second one.

17
Q

symbol

A

Letter

18
Q

terminal symbol

A

An element of the alphabet over which we are trying to create words using a grammar

19
Q

word

A

obtained from concatenating 0 or more letters. Same as a string

20
Q

derviation

A

Way of demonstrating that a particular word is generated by a grammar

21
Q

DFA

A

Deterministic finite automaton

22
Q

GNFA

A

Generalised non deterministic finite automaton. Used to generate regular expressions from automata

23
Q

Language

A

set of words

COMP11212 - Computation (9 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions