automata Flashcards
Every subset of a regular language is regular.
F
The Dyck language is regular.
F
If a language L is generated by some context-free grammar, then L is accepted by some PDA.
T
If L is a language accepted by some PDA, then L is generated by some context-free grammar.
T
The Kleene closure of every context-free language is context-free.
T
If a language has an unambiguous context-free grammar, then it is is accepted by some deterministic push-down automaton.
F
If a language has an ambiguous context-free grammar, then it is is not accepted by any deterministic push-down automaton.
F
There is a PDA that accepts the language consisting of all C++ programs.
F
The intersection of any two context-free languages is context-free
F
The union of any two context-free languages is context-free.
T
The language {a
mbcn : 0 ≤ m ≤ n} is accepted by some DPDA
T
The membership problem for context-free languages is decidable.
T
The equivalence problem for context-free grammars is decidable
F
Every DFA is an NFA.
T
Every regular language is context-free
T
The Kleene closure of every regular language is regular
T
The language consisting of all hexadecimal numerals for positive integers n such that n % 13 = 7
is regular.
T
The complement of every regular language is regular
T
The union of any two regular languages is regular
T
Every NFA is a DFA
F
The intersection of any two regular languages is regular
T
There exists a mathematical proposition that is true, but where no proof of the proposition can
exist.
T
