Discrete Structures Exam 2
Give a production grammar for the language L = {x | x ∈ (a,v)*, the number of a's in x is
a multiple of 3} - ANS-S -> bS | b | aA | bA
A -> aB
B -> bB
B -> aS
The production grammar {S -> aSbb | abb} is - ANS-Type 2 grammar
Which string can be produced by S->aS | bA, A->d | ccA?
a)aabccd
b)adabcca
c)abcca
d)abababd - ANS-a)aabccd
Which of the following statements is wrong?
a) The regular sets are closed under intersection
b) The class of regular sets is closed under substitution
C) The class of regular sets is closed under homomorphism
d)Context Sensitive Grammar(CSG) can be recognized by FSM - ANS-d
The Union of CFL and regular languages
a) is always regular
b) is always context free
c) both a and b
d) need not be regular - ANS-c
Which of the following is undecidable?
a) Membership problem of CFG
b) ambiguity problem for CFG
c)Finiteness problem for FSA
d)Equivalence problem for FSA - ANS-b
Pushdown Automata represents a
a) type 0 grammar
b) type 1 grammar
c) type 2 grammar
d) type 3 grammar - ANS-c
, If every string of a language can be determined whether it is legal or illegal in finite time
the language is called
a) Decidable
b) undecideable
c) Interpretive
d) non deterministic - ANS-a
A context free language can be recognized by
a) Finite State Automaton
b) Linear Bound Automaton
c) Pushdown Automaton
d) both B and C - ANS-d
Which of the following is the most general phase structured grammar?
a) Regular
b) Context sensitive
c) Context free
d) None of the above - ANS-b
The following grammar
S->bS | b
is a
a) type-3 grammar
b) type-2 grammar
c) type-1 grammar
d) type-0 grammar - ANS-a
All strings having equal number of a and b can be recognized by
a) DFA
b) NDFA
c) PDA
d) All of the above - ANS-c
Which of the following statements is false?
a) Context-free languages are closed under union
b) Context-free languages are closed under concatenation
c) Context-free languages are closed under intersection
d) Context-free languages are closed under Kleene closure - ANS-c
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Hkane. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.99. You're not tied to anything after your purchase.
