Language Theory: Context-Free Grammar

What is a context-free grammar?

• A context-free grammar is a formal grammar that describes a formal language in terms of production rules that define how strings of symbols can be formed.

• A context-free grammar is a data structure.

• A context-free grammar is a mathematical equation.

• A context-free grammar is a type of programming language.

What are the four components of a context-free grammar?

• Non-terminal symbols, Terminal symbols, Production rules, Start symbol

• Non-terminal symbols, Terminal symbols, Production rules, End symbol

• Non-terminal symbols, Terminal symbols, Derivation rules, Start symbol

• Non-terminal symbols, Terminal symbols, Production rules, Final symbol

What is a production rule in a context-free grammar?

• A production rule in a context-free grammar is a rule that defines how a nonterminal symbol can be replaced by a sequence of terminal and/or nonterminal symbols.

• A production rule in a context-free grammar is a rule that defines how a terminal symbol can be replaced by a sequence of nonterminal symbols.

• A production rule in a context-free grammar is a rule that defines how a nonterminal symbol can be replaced by another nonterminal symbol.

• A production rule in a context-free grammar is a rule that defines how a nonterminal symbol can be replaced by a sequence of terminal symbols.

What is the difference between a terminal symbol and a non-terminal symbol in a context-free grammar?

• A terminal symbol represents a basic unit of the language, while a non-terminal symbol represents a group of terminal or non-terminal symbols.

• A terminal symbol represents a specific rule in the grammar, while a non-terminal symbol represents a basic unit of the language.

• A terminal symbol represents a basic unit of the language, while a non-terminal symbol represents a specific rule in the grammar.

• A terminal symbol represents a group of terminal or non-terminal symbols, while a non-terminal symbol represents a basic unit of the language.

What is the start symbol in a context-free grammar?

• A terminal symbol

• A production rule

• A regular expression

• A non-terminal symbol

What is the language generated by a context-free grammar?

• A context-free grammar generates a context-free language.

• A context-free grammar generates a context-sensitive language.

• A context-free grammar generates a regular language.

• A context-free grammar generates a regular expression.

What is the Chomsky normal form for a context-free grammar?

• A -> BC or A -> b

• A -> BC or A -> a

• A -> B or A -> C

• A -> a or A -> b

What is the pumping lemma for context-free languages?

• The pumping lemma for context-free languages states that any context-free language L can be divided into six parts: uvwxyz, such that for any i ≥ 0, the string uv^iwx^iyz is also in L, where v and x are non-empty strings.

• The pumping lemma for context-free languages is a property that states that any context-free language L can be divided into five parts: uvxyz, such that for any i ≥ 0, the string u(v^i)x(y^i)z is also in L, where v and y are non-empty strings.

• The pumping lemma for context-free languages states that any context-free language L can be divided into four parts: uvwxy, such that for any i ≥ 0, the string uv^iwx^iyz is also in L, where v and x are non-empty strings.

• The pumping lemma for context-free languages states that any context-free language L can be divided into three parts: uvw, such that for any i ≥ 0, the string uv^iwx^iyz is also in L, where v and x are non-empty strings.

What is the difference between a leftmost derivation and a rightmost derivation in a context-free grammar?

• The difference between a leftmost derivation and a rightmost derivation in a context-free grammar is the number of terminals that are replaced.

• The difference between a leftmost derivation and a rightmost derivation in a context-free grammar is the order in which terminals are replaced.

• The difference between a leftmost derivation and a rightmost derivation in a context-free grammar is the number of non-terminals that are replaced.

• The difference between a leftmost derivation and a rightmost derivation in a context-free grammar is the order in which non-terminals are replaced.

What is the difference between a parse tree and a derivation tree in a context-free grammar?

• A parse tree represents the semantic structure of a sentence, while a derivation tree represents the syntactic structure.

• A parse tree shows the step-by-step derivation of a sentence, while a derivation tree represents the syntactic structure.

• A parse tree represents the syntactic structure of a sentence, while a derivation tree represents the semantic structure.

• A parse tree represents the syntactic structure of a sentence according to the rules of a context-free grammar, while a derivation tree shows the step-by-step derivation of a sentence from the start symbol by applying grammar rules.