FiltersDone

Question type

Essay

Multiple Choice

Short Answer

True False

Matching

Exam 2: Formal Languages and Automata Theory: Part B

Show Answer

Share

---

All types

Filters

Study FlashcardsPractice ExamLearn

Question 1

Multiple Choice

Review LaterAdd Note

Review Later

Which of the following statements is false?

A) Every context-sensitive language is recursive.
B) The set of all languages that are not recursively enumerable is countable.
C) The family of recursively enumerable languages is closed under union.
D) The families of recursively enumerable and recursive languages are closed under reversal

Correct Answer

verified

B

Question 2

Multiple Choice

Review LaterAdd Note

Review Later

Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules S --> aB S --> bA B --> b A --> a B --> bS A --> aS B --> aBB A --> bAA Which of the following strings is generated by the grammar?

A) aaaabb
B) aabbbb
C) aabbab
D) abbbba

Correct Answer

verified

Show Answer

Question 3

Multiple Choice

Review LaterAdd Note

The number of tokens in the following C statement is (GATE 2000) printf("i = %d, &i = %x", i, &i) ;

The regular grammar for the language L = {anbm | n + m is even} is given by

Which of the following are decidable? I. Whether the intersection of two regular languages is infinite II. Whether a given context-free language is regular III. Whether two push-down automata accept the same language IV. Whether a given grammar is context-free

The number of strings of length 4 that are generated by the regular expression (0+1+|2+3+) *, where | is an alternation character and {+, *} are quantification characters, is:

Let be the encoding of a Turing machine as a string over ?= {0, 1}. Let L = { |M is a Turing machine that accepts a string of length 2014 }. Then, L is

Which of the following statements in true?

If L and L' are recursively enumerable, then L is

Let L denotes the language generated by the grammar S - OSO/00. Which of the following is true?

Which of the following is true for the language {a^p} p is prine ?

Consider the following decision problems: (P₁) Does a given finite state machine accept a given string (P₂) Does a given context free grammar generate an infinite number of stings Which of the following statements is true?

Consider the following identities for regular expressions: (a) (r + s) * = (s + r) * (b) (r*) * = r* (c) (r* s*) * = (r + s) * Which of the above identities are true?

For S ? (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5) . Let L = {s ? (0 + 1) * d(s) mod5 = 2 and d(s) mod7 != 4}. Which one of the following statements is true?

Let S and T be language over ={a,b} represented by the regular expressions (a+b*) * and (a+b) *, respectively. Which of the following is true?

Which of the following pairs have DIFFERENT expressive power?

In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?

Which of the following are decidable ? 1) whether the intersection of two regular language is infinite. 2) whether a give context free language is regular 3) whether two push down automata accept the same language. 4) whether a given grammar is context free

Which one of the following is FALSE?

Consider the following two statements: S₁: { 0^2n |n >= l} is a regu1ar language S₂: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar language Which of the following statements is correct?