Question

If L₁ and L₂ are Regular Languages, then L₁  ∪ L₂  is a CFL.

Group of answer choices

True

False

Flag this Question

Question 61 pts

If L₁ and L₂ are CFLs, then L₁  ∩ L₂ and L₁ ∪ L₂ are CFLs.

Group of answer choices

True

False

Flag this Question

Question 71 pts

The regular expression ((ac^*)a^*)^* = ((aa^*)c^*)^*.

Group of answer choices

True

False

Flag this Question

Question 81 pts

Some context free languages are regular.

Group of answer choices

True

False

Flag this Question

Question 91 pts

All finite languages are context-sensitive languages.

Group of answer choices

True

False

Flag this Question

Question 101 pts

A context-free grammar (CFG) can contain the productions:

AB ⟶ bB, A ⟶ a | AB, B ⟶ b.

Group of answer choices

True

False

Flag this Question

Question 111 pts

Every language is generated by some Chomsky type 1 grammar.

Group of answer choices

True

False

Flag this Question

Question 121 pts

There are languages that are neither context-free nor deterministic context-free.

Group of answer choices

True

False

Flag this Question

Question 131 pts

Two pda’s with unequal numbers of states and transitions can accept the same language.

Group of answer choices

True

False

Flag this Question

Question 141 pts

All regular languages are deterministic context-free languages.

Group of answer choices

True

False

Flag this Question

Question 151 pts

Every language is either regular or context-free or context-sensitive.

Group of answer choices

True

False

Flag this Question

Question 161 pts

There is a recursively enumerable language whose complement is not recursively enumerable.

Group of answer choices

True

False

Flag this Question

Question 171 pts

Every Chomsky type 1 language is recursive and every type 0 language is recursively enumerable.

Group of answer choices

True

False

Flag this Question

Question 181 pts

Every TM has some input on which it will run forever.

Group of answer choices

True

False

Flag this Question

Question 191 pts

Every language is decided by some Turing Machine.

Group of answer choices

True

False

Flag this Question

Question 201 pts

All Turing Machines eventually halt on input λ.

Group of answer choices

True

False

Flag this Question

Question 211 pts

The regular expression (a^*ab+ba)^*a^* = (a+ab+ba)^*.

Group of answer choices

True

False

Flag this Question

Question 221 pts

There are CFLs L₁ such that L₁ ≠L(M) for any deterministic pda M.

Group of answer choices

True

False

Flag this Question

Question 231 pts

The language { aⁱb^jc^kd^le^mfⁿ : i, j, k, l, m, n  ≥ 1 } is recursive.

Group of answer choices

True

False

Flag this Question

Question 241 pts

A Chomsky type 0 language is always inherently ambiguous.

Group of answer choices

True

False

Flag this Question

Question 251 pts

The empty string is never in the empty language.

Group of answer choices

True

False

Flag this Question

Question 261 pts

The context-free languages are a proper subset of the context-sensitive languages.

Group of answer choices

True

False

Flag this Question

Question 271 pts

An infinite language contains only strings of finite length.

Group of answer choices

True

False

Flag this Question

Question 281 pts

Every CFL can be described by an infinite number of CFGs.

Group of answer choices

True

False

Flag this Question

Question 291 pts

Every subset of a regular language is regular.

Group of answer choices

True

False

Flag this Question

Question 301 pts

Every leftmost derivation corresponds to a unique parse tree, and vice-versa.

Group of answer choices

True

False

Flag this Question

Question 311 pts

Any infinite regular language properly contains another infinite regular language.

Group of answer choices

True

False

Flag this Question

Question 321 pts

Every subset of a context-free language is context-free.

Group of answer choices

True

False

Flag this Question

Question 331 pts

If L₁ ∩ L₂ is regular, then both L₁ and L₂ must also be regular.

Group of answer choices

True

False

Flag this Question

Question 341 pts

If L(G) is finite, then G is a regular grammar.

Group of answer choices

True

False

Flag this Question

Question 351 pts

A standard TM is equivalent to a PDA with two independent stacks.

Group of answer choices

True

False

Flag this Question

Question 361 pts

Nonregular languages are always infinite.

Group of answer choices

True

False

Flag this Question

Question 371 pts

Nondeterminism adds no power to deterministic finite automata.

Group of answer choices

True

False

Flag this Question

Question 381 pts

An infinite language must contain an infinite number of strings

Group of answer choices

True

False

Flag this Question

Question 391 pts

Nondeterminism adds no power to deterministic PDAs.

Group of answer choices

True

False

Flag this Question

Question 401 pts

Nondeterminism adds no power to deterministic Turing machines.

Group of answer choices

True

False

Flag this Question

Question 411 pts

Every finite language can be generated by a regular expression with no star closures.

Group of answer choices

True

False

Answer 1

Please Note: I have answered the first 4 Questions, according to HOMEWORKLIB RULES. Please Re-Post for receiving answers on the other questions.

Answer)
1. True, if they are individually are Regular then the union is CFL

2. False, L1 ∩ L2 does not need to be context free.

3. False, They can generate different strings for different requirements.

4. True, Not all CFG are regular, thus it is true.

**Please Hit Like if you appreciate my answer. For further doubts on the question or answer please drop a comment, I'll be happy to help. Thanks for posting.**