Learn more about our help with Assignments: Math
Search & Filtering
The set {0,1,#}+-{b1#b2#…#bn|n>=1} where bi is the binary representation of i is
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive
The language {w| w is the set of all balanced parenthesis} is
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive
The language {w| w in {0,1}* and w does not have three consecutive 0′s} is
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive
{w| w has equal number of a’s and b’s } is
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive
The intersection of two cfls can simulate a turing machine computation. We are given two cfls L1 and L2 and define the language L as below
a) L=(00)* if the intersection of L1 and L2 is empty
b) L=((0(00)*)(0(00)*))* if L1 is regular
c) L=(00+0000+000000)* if L2 is not regular
d) L=(00)*+(0000)* if the complement of L1 is a cfl
a) L is a finite set
b) L is a regular set
c) L is undecidable
d) L is recursive but not context-free
a) L=(00)* if the intersection of L1 and L2 is empty
b) L=((0(00)*)(0(00)*))* if L1 is regular
c) L=(00+0000+000000)* if L2 is not regular
d) L=(00)*+(0000)* if the complement of L1 is a cfl
a) L is a finite set
b) L is a regular set
c) L is undecidable
d) L is recursive but not context-free
We are given an arbitrary turing machine M and define the language L as below
L=(0*+1*)* if M halts on blank tape
L=(0+1*)* if M ever prints a 1
L=(0*+1)* if M ever enters a designated state q
L=((0+1+00+11+000+111)+)* if M accepts an infinite set
L=0*(10*)* if M accepts a finite set
L=1*(01*)* if M accepts exactly 45 strings
Choose the correct statement with reference to the string x=00000111111000000111111
a) x is in L
b) x is not in L
c) we can never decide if x is in L as all the problems of the turing machine are undecidable
d) whether x is in L depends on the particular turing machine M
L=(0*+1*)* if M halts on blank tape
L=(0+1*)* if M ever prints a 1
L=(0*+1)* if M ever enters a designated state q
L=((0+1+00+11+000+111)+)* if M accepts an infinite set
L=0*(10*)* if M accepts a finite set
L=1*(01*)* if M accepts exactly 45 strings
Choose the correct statement with reference to the string x=00000111111000000111111
a) x is in L
b) x is not in L
c) we can never decide if x is in L as all the problems of the turing machine are undecidable
d) whether x is in L depends on the particular turing machine M
We are given two context-free languages L1 and L2 and L defined as below
a) L=(0+1)* if L1=L2
b) L=((0+00+000)*(1+11+111)*)* if L1 is contained in L2
c) L=((0(10)*)*(1(01)*)* if L2 is contained in L1
d) L=(00+11+0+1)*(0+00+000)* if L1 and L2 are incomparable
a) As all the conditions relating to L1 and L2 are undecidable we cannot say anything about L
b) L is recursively enumerable
c) L is recursive but not context-sensitive
d) L is context-sensitive but not context-free
e) L is context-free but not regular
a) L=(0+1)* if L1=L2
b) L=((0+00+000)*(1+11+111)*)* if L1 is contained in L2
c) L=((0(10)*)*(1(01)*)* if L2 is contained in L1
d) L=(00+11+0+1)*(0+00+000)* if L1 and L2 are incomparable
a) As all the conditions relating to L1 and L2 are undecidable we cannot say anything about L
b) L is recursively enumerable
c) L is recursive but not context-sensitive
d) L is context-sensitive but not context-free
e) L is context-free but not regular
Nobody knows if P=NP at present. Consider a language L as defined below
L=(0+1)* if satisfiability is in P
L=(0*1)0* if satisfiability is not in P
L=(1*0)1* if 3-sat is in P
L=(0*1*)* if 3-sat is not in P
L=(0*1*0*1*)* if 0/1 knapsack problem is in P
L=(1*0*1*0*)* if 0/1 knapsack problem is not in P
L=(0*(00)*(1*11*)*) * if max-clique problem is in P
L=(0*(00)*(1*11*)*) * if node-cover problem is not in P
L=(0*1*)****(010)* if edge-cover problem is not in P
L=(0* + 1* + (00)* + (11)*)*(0100101010)* if the chromatic problem is not in P
What can we say about the string 0000111100001111=x
a) x is always in L
b) whether x is in L or not will be known after we resolve P=NP
c) the definition of L is contradictory
d) x can never be in L
L=(0+1)* if satisfiability is in P
L=(0*1)0* if satisfiability is not in P
L=(1*0)1* if 3-sat is in P
L=(0*1*)* if 3-sat is not in P
L=(0*1*0*1*)* if 0/1 knapsack problem is in P
L=(1*0*1*0*)* if 0/1 knapsack problem is not in P
L=(0*(00)*(1*11*)*) * if max-clique problem is in P
L=(0*(00)*(1*11*)*) * if node-cover problem is not in P
L=(0*1*)****(010)* if edge-cover problem is not in P
L=(0* + 1* + (00)* + (11)*)*(0100101010)* if the chromatic problem is not in P
What can we say about the string 0000111100001111=x
a) x is always in L
b) whether x is in L or not will be known after we resolve P=NP
c) the definition of L is contradictory
d) x can never be in L
An arbitrary turing machine M will be given to you and we define a language L as follows
L=(0+00)* if M accepts at least one string
L=(0+00+000)* if M accepts at least two strings
L=(0+00+000+0000)* if M accepts at least three strings
———
———
L=(0+00+000+—+0^n) *if M accepts at least n-1 strings
Choose the correct statement.
a) We cannot say anything about L as the question of whether a turing machine accepts a string is undecidable
b) L is context-sensitive but not regular
c) L is context-free but not regular
d) L is not a finite set
L=(0+00)* if M accepts at least one string
L=(0+00+000)* if M accepts at least two strings
L=(0+00+000+0000)* if M accepts at least three strings
———
———
L=(0+00+000+—+0^n) *if M accepts at least n-1 strings
Choose the correct statement.
a) We cannot say anything about L as the question of whether a turing machine accepts a string is undecidable
b) L is context-sensitive but not regular
c) L is context-free but not regular
d) L is not a finite set
Given an arbitrary context free grammar G, we define L as below.
L=(0+1)* if G is ambiguous
And
L=j if G is not ambiguous
Which of the following is true?
a. L is a context-free language
b. L is recursive but not r.e.
c. What L is depends on whether we can determine if G is ambiguous or not
d. What L is is undecidable
L=(0+1)* if G is ambiguous
And
L=j if G is not ambiguous
Which of the following is true?
a. L is a context-free language
b. L is recursive but not r.e.
c. What L is depends on whether we can determine if G is ambiguous or not
d. What L is is undecidable
Finding a professional expert in "partial differential equations" in the advanced level is difficult.
You can find this expert in "Assignmentexpert.com" with confidence.
Exceptional experts! I appreciate your help. God bless you!
#340153 on Dec 2023
#340153 on Dec 2023