Flashcards
SCC 312
Cards in this deck (36)
- 1Define an alphabetThis is a finite set of symbols (Symbols are atomic, meaning there are no duplicate symbols)
- 2Define a StringA sequence of the atomic symbols taken from a finite alphabet
- 3Define a LanguageThis is the complete set of strings that can be formed from the symbols of an alphabet
- 4Define a sentenceWhen a string is a member of the language it is called a sentence of the language
- 5What is the operation Length?The number of symbols in the string x
Written |x| - 6What is the operation Concatentation?The string formed by the string x followed by the string y
- 7What is the operation Power?The string formed by writing down n copies of the string x
- 8What is the operation Index?the nth symbol in the string x (Always start counting from 1)
- 9Define what is meant by the term "a set Definition of a language"?If a language is such that the strings follow certain patterns we are able to specify it by providing a set definition
- 10What are the three parts of a set definition?The function to produce the string
Is "such that"
The range of arguments to the function - 11Define a Decision ProgramInput a string and the program tells you if the string belongs to the language
- 12Define GrammarA set of rules for defining which strings are grammatical and which are not.
Grammars don't give us the meaning of a sentence - 13What is meant by the term "a formal grammar"?This defines which strings are grammatical and which are not.
For the grammatical strings it prescribes the structure of the string - 14What is Derivation when it comes to grammars (What are the steps in derivation)?Start with the first symbol
Search for a sequence in the current string that matches the left-hand side of the rule
Replace the sequence with the right-hand side of the rule
continue until it gets stuck or has a valid string
try all possible derivations from the first symbol will give us all the grammatical strings of the language
This is Top-down, Depth-first search - 15What is ParsingThis is given a string, what productions would we need to derive it from the first symbol. This is the basic principle of compilers and is bottom-up
- 16What are the four parts of a Phrase Structure Grammar?A set of basic objects of the language
A set of things like NOUN-PHRASE or CONDITION
Contains a particular non-terminal with which we always start the derivation of a valid sentence
A set of productions or rules of the grammar - 17What are type 3 grammars?Regular Grammars
- 18What are the production formats for regular grammar?NON-TERMINAL ---> terminal NON-TERMINAL
NON-TERMINAL ---> terminal - 19What is the "language generated by the grammar"?The set containing each and every string of terminal symbols that can be generated by a grammar
- 20What is the subset Construction Algorithm?To convert a non-deterministic FSR into a deterministic FSR and can be used on any non-deterministic FSR
- 21What are the three steps in Subset Construction Algorithm1) Mark the start state
2) For each rule group together all the non-terminals that are preceded by the same terminal. the new set of non-terminals forms a new state in the FSR
3) Repeat step two until complete - 22What are Regular Expressions?These are a set of rules that describe a generalised string
- 23What are Regular Expressions made up of?Individual symbols/characters and specific quantifiers
There are four Specific Quantifiers:
1) * = zero or more instances of the atom
2) + = one or more instances of the atom
3) ? = zero or one instances of the atom - 24Describe the "Repeat State" Theorem and what are the three parts to it (the letters)The string that is accepted can be expressed as three concatenated sub-strings:
v = the string accepted before the repeated state/s
w = the repeated string
x = the string accepted after the repeat state/s - 25What is the production format for Context-Free Grammars?X ---> RHS
X is a single non-terminal
RHS is any mixture of terminals and/or non-terminals (can also be empty) - 26What is a Pushdown Recogniser (PDR)?This is a finite state machine with extra storage
- 27What is in the stack of a PDR?It has two procedures: pop and push
can only add and remove from the top of the stack and can contain terminals and nonterminals
It is formatted pop/read/push in that order - 28What is meant by the term ambiguity?This means that within a language one or more sentences can be parsed into more than one structure
A sentence is ambiguous if it can be parsed according to a grammar in at least two different ways - 29What is the "uvwxy" theoremThe string accepted can be expressed as five concatenated substrings:
u and y are the strings accepted before and after the repeated states
v and x are the repeated strings
w is the string accepted between v and x - 30What is the format for Context-Sensitive GrammarsLHS ---> RHS
LHS = mixture of terminals and/or non-terminals, but there must be at least one symbol (cannot be empty)
RHS = any mixture of terminals and/or non-terminals, but cannot be the empty string
LHS <= RHS - 31What is the format for Unrestricted GrammarsLHS ---> RHS
LHS = any mixture of terminals and/or non-terminals, but there must be at least one symbol
RHS = any mixture of terminals and non-terminals and can be the empty string
there is no length restriction on RHS - 32What is a Turing Machine?Reads symbols from an input string called the tape and changes states, like a finite state recogniser
can write onto the tape and read it back - 33Explain how the Turing machine tape is split/divided and used?The tape is divided into squares and is infinite in both directions
Each square contains a single symbol from the alphabet of the language - 34What are the instructions on a Turing Machine?The symbol to read from the input tape square
The new symbol to write to the square
The direction to move the r/w head - 35What is a Linear Bonded Turing Machine?This is restricted to the space required for the input string plus a fixed number of extra squares
this is used for context-sensitive grammars because the RHS never gets smaller than the LHS - 36—
Information
- Description
- Flashcards on SCC 312, created by Robert Carr on 03/05/2018.
- Created by
- Robert Carr
- Views
- 0
- Rating