CS 4.3. (ALEVEL) - Context-Free Languages

Question 1

Context-Free Languages

Answer 1

set of strings and symbols that follow rules of a context-free grammar.
-context free grammar = which strings are not possible by laying out production rules
e.g. a → ab
This rule specifies that the a
character can be replaced
by the two characters ab .

Question 2

Backus-Naur Form

Answer 2

-way of notating context-free languages
-can use recursion
e.g. <Integer> ::= <Digit>|<Digit><Integer></Integer></Digit></Digit></Integer>

Question 3

Non-terminals

Answer 3

• can be broken down further into more non-terminals or terminals
  e.g. <FullName> ::= <Title><Forename><Surname></Surname></Forename></Title></FullName>

Question 4

Terminals

Answer 4

• cannot be broken down any further, must be taken to be the written value

Question 5

Syntax Diagrams

Answer 5

Visual Representation of regular language
- rectangles = non-terminals
- ellipsis = terminals
-