NET Questions TOC QUESTIONS
True or False
- In a finite language no string is pumpable. True
- A DFA has infinite number of states. False
- 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
