A DFA can have more than one accepting state. True
In DFA all states have same number of transitions. True
Every subset of a regular language is regular. False
Let L4 = L1L2L3. If L1 and L2 are regular and L3 is not regular, it is possible that L4 is regular. True
In a finite language no string is pumpable. True
If A is a nonregular language, then A must be infinite. True
Every context-free language has a context-free grammarin Chomsky normal form. True
If A is a context-free language, then A must be nonregular. False
The class of regular languages is closed under intersection. True
If a language A is regular, then it A must be finite. False
Every language is Turing-recognizable. False
If a language is context-free, then it must be Turing-decidable. True
The problem of determining if a context-free grammar generates
the empty language is undecidable. False
The problem of determining if a Turing machine recognizes the
empty language is undecidable. True
The set of all languages over an alphabet is countable.False
There are some languages recognized by a 5-tape, nondetermin-
istic Turing machine that cannot be recognized by a 1-tape,
deterministic Turing machine.False
The language { 0n1n | 0 ≤ n ≤ 1000 } is regular. True
Nonregular languages are recognized by NFAs. False
The class of context-free languages is closed under intersection. False
A language has a regular expression if and only if it
has an NFA. True
The regular expression (01*0 ∪ 1)*0 generates the language
consisting of all strings over {0, 1} having
an odd number of 0’s. False
If a language A has a PDA, then A is generated by a
context-free grammar in Chomsky normal form. True
If A is a context-free language and B is a language such that B is a subset of A, then B must be a context-free language. False
If a language A has an NFA, then A is nonregular. False
The regular expressions (a ∪ b)* and (b*a*)* generate the same language. True
If a language A has a regular expression, then it also has a context-free grammar. True
No comments:
Post a Comment