LP Flashcards
(74 cards)
What is a language?
A language is a set of symbols/tokens and a set of (possibly empty) strings and tokens.
What is the purpose of formal grammar?
The purpose of formal grammar is to generate languages. Using formal grammar, we can verify whether a sentence is in the language and synthesize legal problems.
What is V in formal grammar?
In formal grammar, V stands for vocabulary, which is a set of symbols.
How is V partitioned in formal grammar?
V is partitioned into two subsets of terminal and nonterminal symbols in formal grammar.
What is V* in formal grammar?
In formal grammar, V* is the set of all strings of elements of V, including the empty string. This is called the closure of V.
What is the set + in formal grammar?
In formal grammar, + is the set of non-empty strings of elements of V.
What does ε represent in formal grammar?
In formal grammar, ε represents the empty string, often informally written as ‘ ’ or “ “.
Can you give an example of a vocabulary V in formal grammar?
Sure. A vocabulary V could be {0, 1, +, -, *, (, ), <exp>}, where <exp> is a non-terminal symbol, and all other symbols are terminal.</exp></exp>
Can you give an example of sentences in a vocabulary V in formal grammar?
Sure. Example sentences in a vocabulary V {0, 1, +, -, *, (, ), <exp>} could be ε, 1 + 1, (1 + 1) and (1 + (1)), ((((, and (()) * --.</exp>
What do alpha, beta, and gamma range over in formal grammar?
In formal grammar, alpha, beta, and gamma range over strings.
What is a production rule in formal grammar?
A production rule is a pair alpha ::= beta, where alpha is a nonterminal symbol, and beta is a string of terminals and/or nonterminals.
What is an example vocabulary V in formal grammar?
An example vocabulary V in formal grammar could be {0, 1, +, -, *, (, ), <exp>}.</exp>
What are some example production rules for the given vocabulary V?
Some example production rules for the given vocabulary V {0, 1, +, -, *, (, ), <exp>} are:</exp>
<exp> ::= 0
<exp> ::= 1
<exp> ::= -<exp>
<exp> ::= (<exp>)
<exp> ::= <exp>+<exp>
<exp> ::= <exp>*<exp>
</exp></exp></exp></exp></exp></exp></exp></exp></exp></exp></exp></exp>
Definition of regular grammar:
Regular grammar is formal grammar that generates only regular languages, which can be recognised by a DFA or NFA.
Rules in form A -> aB or A -> a where A and N are non-terminals and a is terminal.
Regular grammars are of type 3.
Definition of context-free grammar:
Formal grammar in which each production rule has a single non-terminal symbol on its left-hand side and on the right-hand side 0 or more terminals or non-terminals.
Used to describe the syntax of programming and natural languages.
A language is context-free if there exists a cfg that generates it.
CFG grammars are of type 2.
S -> NP VP
NP -> Det N
VP -> V NP
Det -> the
N -> cat | mouse
V -> chased
Left-regular grammar:
When Terminals are on the left:
- A -> a
- A -> Ba
- A -> e
Right-regular grammar:
When non-terminals are on the right:
- A -> a
- A -> aB
- A -> e
Write grammar that generates the following language, over the alphabet {0, 1}:
{0}.
S -> 0
Write grammar that generates the following language, over the alphabet {0, 1}:
{1, 10, 100, 1000, . . .}
S -> 1T | 1
T -> OT | e
Write grammar that generates the following language, over the alphabet {0, 1}:
The set of strings over 0 and 1 that contain at least three consecutive repeated characters. So 100110 and ϵ are not in the language,
and 000 and 111 and 01000110 are in the language.
S → 0SS | 1SS | A
A → 000A | 111A | B
B → 000B | 111B | ε
Write grammar that generates the following language, over the alphabet {0, 1}:
The set of strings over 0 and 1 that contain no three consecutive
repeated characters. So 100110 and ϵ are in the language, and
000 and 111 and 01000110 are not.
S → 0A | 1A | ε
A → 01B | 10B | 0S | 1S
B → 01C | 10C | ε
C → 0B | 1B | ε
write a regular grammar to
recognise ( {a3^n| n ≥ 0}
S → aB | ε
B → aC
C → aS
write a regular grammar to
recognise {(abba)∗}
S -> aB | ε
B -> bC
C -> bD
D -> aS
Write a grammar for the language of properly bracketed high school
arithmetic over single binary digits. So:
* the set of terminal symbols is {0, 1, +, ×,(,)}, and
* 0 and 1 and (0) and 1+1 and 1+0×1 and 1+ (0×1) and (1+1)×1
are in the language, and
* 01 and 1 + (1 and () are not in the language.
<exp> ::= <term> | <term> + <exp> | <term> - <exp>
<term> ::= <factor> | <factor> × <term>
<factor> ::= <digit> | (<exp>)
<digit> ::= 0 | 1
</digit></exp></digit></factor></term></factor></factor></term></exp></term></exp></term></term></exp>