Question 1

Consider the languages: L₁ ={a^n b^n c^m | n,m >01 and L₂ ={a^n b^m c^m |n,m> o) Which one of the following statements is FALSE? A)L₁ n L₂ is a context-free language B)L₁ u L₂ is a context-free language C)L₁ and L₂ are context-free languages D)L₁ n L₂ is a context sensitive language

Accepted Answer

The answer of Consider the languages: L₁ ={a^n b^n c^m...

Question 2

Let L₁ be a recursive language, and let L₂ be a recursively enumerable but not a recursive language. Which one of the following is TRUE? A)L₁' is recursive and L₂' is recursively enumerable B)L₁' is recursive and L₂' is not recursively enumerable C)L₁' and L₂' are recursively enumerable D)L₁' is recursively enumerable and L₂' is recursive

Accepted Answer

The complement of a recursive language (L₁') is recursive, but the complement of a recursively enumerable language that is not recursive (L₂') is not recursively enumerable.

Question 3

Consider the following two problems on undirected graphs:
?: Given G(V,E), does G have an independent set of size |v|-4?
?: Given G(V,E), does G have an independent set of size 5?
Which one of the following is TRUE?
A)? is in P and ? is NP-complete
B)? is NP complete and ? is in P
C)Both ? and ? are NP-complete
D)Both ? and ? are in P

Accepted Answer

The answer of Consider the following two problems on undirected...

Question 4

Let L₁ be a recursive language. Let L₂ and L₃ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true? A)L₂ - L₁ is recursively enumerable. B)L₁ - L₃ is recursively enumberable C)L₂ intersection L₁ is recursively enumberable D)L₂ union L₁ is recursively enumberable

Accepted Answer

The difference between a recursive language and a recursively enumerable but not recursive language is not guaranteed to be recursively enumerable. This is because while you can enumerate the elements of the recursive language, you cannot effectively enumerate the non-elements of the recursively enumerable but not recursive language to perform the subtraction.

Question 5

S -> aSa| bSb| a| b ; The language generated by the above grammar over the alphabet {a,b} is the set of
A)All palindromes.
B)All odd length palindromes.
C)Strings that begin and end with the same symbol
D)All even length palindromes.

Accepted Answer

The grammar generates strings that are palindromes with an odd length, as it recursively adds matching 'a' or 'b' on both sides of the string, starting with a single 'a' or 'b'.

Quiz 1: Formal Languages and Automata Theory: Part A

Consider the languages: L₁ ={a^n b^n c^m | n,m >01 and L₂ ={a^n b^m c^m |n,m> o) Which one of the following statements is FALSE?

Let L₁ be a recursive language, and let L₂ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

Consider the following two problems on undirected graphs: ?: Given G(V,E) , does G have an independent set of size |v|-4? ?: Given G(V,E) , does G have an independent set of size 5? Which one of the following is TRUE?

Let L₁ be a recursive language. Let L₂ and L₃ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

S -> aSa| bSb| a| b ; The language generated by the above grammar over the alphabet {a,b} is the set of

Quiz 1: Formal Languages and Automata Theory: Part A

Consider the languages: L1 ={a^n b^n c^m | n,m >01 and L2 ={a^n b^m c^m |n,m> o) Which one of the following statements is FALSE?

Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

Consider the following two problems on undirected graphs: ?: Given G(V,E) , does G have an independent set of size |v|-4? ?: Given G(V,E) , does G have an independent set of size 5? Which one of the following is TRUE?

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

S -> aSa| bSb| a| b ; The language generated by the above grammar over the alphabet {a,b} is the set of

Consider the languages: L₁ ={a^n b^n c^m | n,m >01 and L₂ ={a^n b^m c^m |n,m> o) Which one of the following statements is FALSE?

Let L₁ be a recursive language, and let L₂ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

Let L₁ be a recursive language. Let L₂ and L₃ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?