Term
|
Definition
|
|
Term
|
Definition
| a language that is accepted by a DFA |
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
| What does it mean to say that the regular languages are closed under the regular operation concatenation? |
|
Definition
| Concatenation of two regular languages is itself a regular language. |
|
|
Term
| T/F: ԑ is a member of some, but not all, power sets |
|
Definition
| False: Power sets have sets of elements |
|
|
Term
| T/F: ԑ is a member of every power set |
|
Definition
| False: ԑ is not a set and so it is not in any power set |
|
|
Term
| T/F: ԑ is a member of some, but not all languages |
|
Definition
| True: some languages contain the empty string, some do not |
|
|
Term
| T/F: ԑ is a member of every language |
|
Definition
| False: some languages contain the empty string, some do not |
|
|
Term
| T/F: ԑ is a member of some, but not all alphabets |
|
Definition
| False: ԑ is never a member of an alphabet |
|
|
Term
| T/F: ԑ is a member of every alphabet |
|
Definition
| False: ԑ is never a member of an alphabet |
|
|
Term
|
Definition
| False: ԑ is not a set and so it is not a language |
|
|
Term
|
Definition
| True: it is a language containing only the empty string |
|
|
Term
|
Definition
| True: the empty set is a subset of all sets, and so it is in every power set |
|
|
Term
| T/F: ∅ is a member of some, but not all, power sets |
|
Definition
| False: The empty set is a subset of all sets, and so is every power set |
|
|
Term
| T/F: {∅} is a member of every power set |
|
Definition
| True: The empty set is a subset of all sets, and so is every power set |
|
|
Term
|
Definition
| False: it is not a language because {∅} is not a string |
|
|
Term
| Which defines a broader set of languages: DFA, NFA, Neither, or It depends. |
|
Definition
| Neither: DFA and NFA have equivalent power because for every DFA we can define an equivalent NFA and vice versa |
|
|
Term
|
Definition
| if some turing machine recognizes it |
|
|
Term
|
Definition
| if some turing machine decides it |
|
|
Term
|
Definition
| A language is computable if a Turing Machine computes it |
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
| Rec or Dec: A-TM^c (ie A-TM bar) |
|
Definition
|
|
