WorksheetsTheory of computation_Quiz3
Total questions: 10
Worksheet time: 5mins
What does CFG stand for in formal language theory?
Context-Free Grammar
Context-Free Generator
Contextual Function Grammar
Combinatorial Formal Grammar
Which of the following is a characteristic of a context-free grammar?
Production rules with a single non-terminal on the left-hand side.
Production rules that require a specific order of symbols.
Production rules that can only generate terminal symbols.
Production rules with multiple non-terminals on the left-hand side.
What is the primary purpose of a pushdown automaton?
To simulate finite automata.
To generate context-free grammars.
To parse regular languages.
To recognize context-free languages.
In a CFG, what does a terminal symbol represent?
Terminal symbols represent the actual content of the language in a CFG.
Terminal symbols are used to define the structure of the grammar.
Terminal symbols are placeholders for non-terminal symbols.
Terminal symbols represent the rules of the grammar.
Which of the following languages can be recognized by a pushdown automaton?
Regular languages
Finite automata languages
Context-free languages
Context-sensitive languages
What is the main difference between a finite automaton and a pushdown automaton?
A finite automaton can recognize context-free languages, while a pushdown automaton cannot.
A pushdown automaton is a type of finite automaton with no memory capabilities.
The main difference is that a pushdown automaton has a stack for memory, allowing it to recognize context-free languages, while a finite automaton does not.
Both finite automata and pushdown automata use a tape for memory storage.
In a context-free grammar, what does a production rule define?
A production rule defines the termination of a string.
A production rule defines the grammar's syntax rules.
A production rule defines the order of terminal symbols.
A production rule defines the substitution of a non-terminal symbol with a sequence of symbols.
Which of the following is true about context-free languages?
Context-free languages can be generated by context-free grammars.
Context-free languages cannot be parsed by any algorithm.
Context-free languages are a subset of context-sensitive languages.
Context-free languages can only be generated by regular grammars.
What is the role of the stack in a pushdown automaton?
The stack helps in executing arithmetic operations.
The stack allows the pushdown automaton to manage context and recognize context-free languages.
The stack is used to store input symbols only.
The stack is primarily for memory management.
Which of the following grammars is not context-free?
{a^n c^n | n ≥ 0}
{a^n b^n | n ≥ 0}
{a^n b^n c^n | n ≥ 0}
{a^n b^n d^n | n ≥ 0}
