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 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

A) 1 and 2
B) 1 and 4
C) 2 and 3
D) 2 and 4

Correct Answer

verified

Show Answer

Question 2

Multiple Choice

Review LaterAdd Note

Review Later

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:

A) 08
B) 09
C) 10
D) 12

Correct Answer

verified

Show Answer

Question 3

Multiple Choice

Review LaterAdd Note

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?

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?

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

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?

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

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

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

Which of the following pairs have DIFFERENT expressive power?

Which of the following statements is false?

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

Which of the following statements in true?

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?

Which one of the following is FALSE?

Let L denotes the language generated by the grammar S - OSO/00. Which of the following 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?

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?

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 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