Week 2 - Context-Free Grammers Flashcards
What is a context-free grammer?
A more powerful way of descibing languages with certain recursive syntactic features.
Give an example of a rescursive syntactic feature.
001 = {0, 00, 000, 0…0, 0…01, 0…011, …} and so on
What are context-free languages?
Languages defined by context-free grammers. The consist of the words that can be genertated by a given context-free grammer.
TRUE OR FALSE: All context-free languages are regular languages.
FALSE.
TRUE OR FALSE: All regular languages are context-free languages.
TRUE
What is a grammer?
A collection of substitution rules. It generates all the strings in a language.
What is a substitution rule?
A subsititution rule is a rule that is applied to symbols to help form a word (aka. derivation) in a grammer.
It consists of symbols and terminals.
Single Symbol -> Symbols and/or Terminals
What does using a substitution rule obtain?
A string called a derivation. Derivations can be represented by a parse tree.
How do you get a word in a language using substitution rules in a grammer?
You start with the start variable. And then apply any appropriate rule to any smbol or combinitation of adjacent symbols. Replace thoses symbol(s) in the string with the symbols at the other side of the substitution rule. Repeat this step until there are no longer any rules that can be applied to your string.
What is an easier way to write these two substitution rules?
A -> 01
A -> B
A -> 01 | B
Define the context-free grammer in computional terms.
A context-free grammer is a tuple G = (V, Σ, R, S), where
o V is a finite set of variables
o Σ is a finite set of terminals, V ∩ Σ = Ø
o R is a finite set of rules, (a rule being composed from a variable and a string from V ∪ Σ)
o S ∈ V is the start variable
How do you represent a derivation occuring to a string?
string => string
The => is important
