Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged closure-property
1
votes
1
answer
61
closure property
CFL over a single alphabet are always-> A. dcfl B. regular C. dcfl but not regular d. non regular
CFL over a single alphabet are always->A. dcflB. regularC. dcfl but not regulard. non regular
raviyogi
668
views
raviyogi
asked
Dec 30, 2017
Theory of Computation
theory-of-computation
context-free-language
closure-property
regular-language
+
–
0
votes
1
answer
62
Some basic properties
1. Turing Decidable means Recursive language 2. Turing recognizable means REL 3. Decidable means Recursive 4. Undecidable means REL or Turing Recognizable. Does the 4th statement is correct or not . Plz give valid assertions and reasons.
1. Turing Decidable means Recursive language2. Turing recognizable means REL3. Decidable means Recursive4. Undecidable means REL or Turing Recognizable. Does the ...
dragonball
328
views
dragonball
asked
Dec 20, 2017
Theory of Computation
theory-of-computation
closure-property
+
–
0
votes
0
answers
63
Closure properties
Subset of Regular Language is REL or not ? PLz Explain with an Example.
Subset of Regular Language is REL or not ?PLz Explain with an Example.
dragonball
513
views
dragonball
asked
Dec 20, 2017
Theory of Computation
theory-of-computation
closure-property
+
–
0
votes
0
answers
64
Toc epsilon closure
Given transition for a $\epsilon$-NFA for p => $\delta (p,\epsilon ) = \left \{ q,r \right \}$ . The question asks for |$\epsilon$-closure(p)| = ? Given answer is 2 {q,r} but should it not be {p,q,r} as p itself is transition state of $\epsilon$-closure(p) ?
Given transition for a $\epsilon$-NFA for p = $\delta (p,\epsilon ) = \left \{ q,r \right \}$ . The question asks for |$\epsilon$-closure(p)| = ? Given answer is 2 {q,r} ...
sumit chakraborty
976
views
sumit chakraborty
asked
Dec 5, 2017
Theory of Computation
theory-of-computation
closure-property
+
–
0
votes
1
answer
65
TOC closure property doubt
If a language L1 is given as anbn and L2 is given as {a,b}* , then the language L1 - L2 will be : regular or CFL and why ? My doubt is that since L2 is a regular language and L1 is CFL and L2 will contain all strings in L1, so ... ). Complement of regular is regular and intersection of CFL with regular is closed and the language will be CFL. Which one is right and why ?
If a language L1 is given as anbn and L2 is given as {a,b}* , then the language L1 - L2 will be : regular or CFL and why ?My doubt is that since L2 is a regular language...
sumit chakraborty
537
views
sumit chakraborty
asked
Nov 29, 2017
Theory of Computation
theory-of-computation
closure-property
context-free-language
regular-language
+
–
4
votes
0
answers
66
Proof of Decidability and Closure properties of various language ?
Hi Guys, If someone can provide proof or some kind of intuition for following properties then it will be great help. Because many problem could be solved via these two tables. https://gatecse.in/grammar-decidable-and-undecidable-problems/ https://gatecse.in/closure-property-of-language-families/ PS: Mainly for CFL, CSL, REC and RE.
Hi Guys,If someone can provide proof or some kind of intuition for following properties then it will be great help. Because many problem could be solved via these two tab...
Chhotu
538
views
Chhotu
asked
Nov 19, 2017
Theory of Computation
theory-of-computation
closure-property
decidability
+
–
1
votes
0
answers
67
Intersection of Different languages
please help me .How to fill this table?
please help me .How to fill this table?
Parshu gate
338
views
Parshu gate
asked
Nov 10, 2017
Theory of Computation
theory-of-computation
closure-property
+
–
2
votes
1
answer
68
Ace Test Series: Theory Of Computation - Closure Property
please explain:
please explain:
raviyogi
848
views
raviyogi
asked
Nov 4, 2017
Theory of Computation
ace-test-series
theory-of-computation
bad-question
closure-property
+
–
2
votes
2
answers
69
Right Quotient
$L_{1}=\left\{a^{n}b^{n}c^{n}|n>=0\right\}\\ L_{2}=\left\{b^{i}c^{j}|i,j>=0\right\}\\ Find \ out\ L_{1}/L_{2}$
$L_{1}=\left\{a^{n}b^{n}c^{n}|n>=0\right\}\\L_{2}=\left\{b^{i}c^{j}|i,j>=0\right\}\\Find \ out\ L_{1}/L_{2}$
Prabhanjan_1
1.4k
views
Prabhanjan_1
asked
Nov 3, 2017
Theory of Computation
theory-of-computation
closure-property
regular-language
+
–
4
votes
1
answer
70
Question regarding DCFL Closure Properties
May someone please explain via simple Set Theory Basics that why DCFL is "not" closed under - 1) UNION 2) INTERSECTION 3) SET DIFFERENCE but is "closed" under complement. Things I know - a) DCFL is proper subset of CFL Thank you! I'm being forced to By Heart them, but I don't want to.
May someone please explain via simple Set Theory Basics that why DCFL is "not" closed under - 1) UNION 2) INTERSECTION 3) SET DIFFERENCE but is "closed" under complement....
iarnav
2.1k
views
iarnav
asked
Nov 1, 2017
Theory of Computation
theory-of-computation
closure-property
context-free-language
+
–
3
votes
1
answer
71
Self Doubt Closure Properties of CFL
If L1 = Regular L and L2 = CFL then L1 UNION L2? = L1 U L2 = Reg L U CFL = CFL U CFL = CFL is it True?
If L1 = Regular L and L2 = CFL then L1 UNION L2?= L1 U L2= Reg L U CFL= CFL U CFL= CFL is it True?
iarnav
554
views
iarnav
asked
Nov 1, 2017
Theory of Computation
theory-of-computation
closure-property
regular-language
context-free-language
+
–
2
votes
0
answers
72
TOC - Micheal Sipser - Regular languages
How to prove shuffle ,perfect shuffle and Drop-out property of Regular languages ?
How to prove shuffle ,perfect shuffle and Drop-out property of Regular languages ?
Prajwal Bhat
540
views
Prajwal Bhat
asked
Oct 24, 2017
Theory of Computation
theory-of-computation
regular-language
closure-property
+
–
3
votes
1
answer
73
Closure Property
L3 and L4 are CFL,L5 is regular. L1=(L3 Union L4)c L2=(L3R Union L4) Intersection L5 L1 and L2 are a.Both CFL b.CSL and CFL c.Recursive and CFL d.None of these
L3 and L4 are CFL,L5 is regular.L1=(L3 Union L4)cL2=(L3R Union L4) Intersection L5L1 and L2 area.Both CFLb.CSL and CFLc.Recursive and CFLd.None of these
Mohammed Sumair
514
views
Mohammed Sumair
asked
Oct 14, 2017
Theory of Computation
theory-of-computation
closure-property
+
–
3
votes
0
answers
74
Closure Properties
Which of the following are closed/ not closed under infinite Union? a.DCFL b.CFL c.CSL d.Recursive Languages e.Recursively enumerable languages
Which of the following are closed/ not closed under infinite Union?a.DCFLb.CFLc.CSLd.Recursive Languagese.Recursively enumerable languages
Mohammed Sumair
410
views
Mohammed Sumair
asked
Oct 14, 2017
Theory of Computation
closure-property
theory-of-computation
+
–
1
votes
1
answer
75
Closure
Context-free grammar is closed over intersection true/false.
Context-free grammar is closed over intersection true/false.
Sunil8860
304
views
Sunil8860
asked
Aug 16, 2017
CO and Architecture
theory-of-computation
closure-property
+
–
1
votes
0
answers
76
Properties of Regular Language with Non- regular Language
Can anyone elaborate the properties of regular language with non regular under union, intersection, set difference , complement etc.
Can anyone elaborate the properties of regular language with non regular under union, intersection, set difference , complement etc.
dragonball
520
views
dragonball
asked
Aug 16, 2017
Theory of Computation
theory-of-computation
regular-language
closure-property
+
–
0
votes
1
answer
77
Test by Bikram | Theory of Computation | Test 2 | Question: 4
Which of the following statements is FALSE? Recursive Enumerable Languages are not closed under set difference and complementation. Complement of context-free language must be recursive. If a problem $X$ is NP complete and $X \in P,$ then $NP = P$. Membership problem is not decidable for Recursive Languages.
Which of the following statements is FALSE?Recursive Enumerable Languages are not closed under set difference and complementation.Complement of context-free language must...
Bikram
414
views
Bikram
asked
Aug 12, 2017
Theory of Computation
tbb-toc-2
theory-of-computation
closure-property
p-np-npc-nph
+
–
1
votes
0
answers
78
Properties
1.Let L be a CFL and R be a Regular language then L $\cap$ R = GIVEN:- always CFL and need not be Regular BUT WHY NOT:- always CFL as well as always Regular R - L = GIVEN:- always CSL and need not be CFL BUT WHY NOT:- always CSL as well as ... R - D = GIVEN:- always DCFL and need not be Regular BUT WHY NOT:- always DCFL as well as always Regular PLEASE GIVE DETAIL EXPLANATION WHY NOT??
1.Let L be a CFL and R be a Regular language then L $\cap$ R =GIVEN:- always CFL and need not be Regular BUT WHY NOT:- always CFL as well as always RegularR - L =GIVEN...
learner_geek
177
views
learner_geek
asked
Aug 4, 2017
Theory of Computation
closure-property
regular-language
theory-of-computation
+
–
0
votes
1
answer
79
#PropertiesOfRegularLanguage
Union & Concatenation property of regular language are closed for both DFA & NFA. But while doing union or concatenation of 2 DFAs, we have to insert epsilon transition between both. Adding epsilon doesn't leave DFA as DFA but make them epsilon-NFA. So is both property closed for DFA?
Union & Concatenation property of regular language are closed for both DFA & NFA. But while doing union or concatenation of 2 DFAs, we have to insert epsilon transition b...
Swati Rauniyar
699
views
Swati Rauniyar
asked
Jul 7, 2017
Theory of Computation
closure-property
regular-language
finite-automata
+
–
1
votes
0
answers
80
Closure properties
Is ((ab)*,+) closed or not closed?
Is ((ab)*,+) closed or not closed?
Kaustubh _15
494
views
Kaustubh _15
asked
Jul 5, 2017
Theory of Computation
theory-of-computation
closure-property
regular-language
+
–
1
votes
1
answer
81
clouser property of regular language
What is the difference between substitution property, homomorphism property and inverse homomorphism property? Give an example to best support your answer.
What is the difference between substitution property, homomorphism property and inverse homomorphism property?Give an example to best support your answer.
Shubhanshu
1.2k
views
Shubhanshu
asked
Jul 2, 2017
Theory of Computation
theory-of-computation
regular-language
closure-property
+
–
0
votes
1
answer
82
Are all languages closed under regular intersection?
ashish pal
347
views
ashish pal
asked
Jun 30, 2017
Theory of Computation
closure-property
theory-of-computation
+
–
1
votes
1
answer
83
Theory of Computation Closure Properties
We know Regular Union CFL is CFL as they are closed but a doubt came in my mind if Regular - (a+b)* CFL - anbn Isn't it regular (a+b)* U anbn = (a+b)* Then how come this statement Regular Union CFL is CFL as they are closed is true ?? Please correct me if i am wrong..
We know Regular Union CFL is CFL as they are closed but a doubt came in my mind ifRegular - (a+b)*CFL - anbn Isn't it regular (a+b)* U anbn = (a+b)* Then how come th...
Himanshu Goyal
790
views
Himanshu Goyal
asked
Jun 29, 2017
Theory of Computation
theory-of-computation
closure-property
+
–
4
votes
1
answer
84
CFL and DCFL
If L1 = { anbncm | n.m >0 } L2 = { anbmcm | n, m > 0} Which of these following are false? 1) L1 ∩ L2 is CFL. 2) L1 ∪ L2 is CFL. 3) L1 and L2 are CFL. 4) L1 ∩ L2 is CSL. I think (1) is FALSE as L1 ∩ L2 becomes CSL. PLease correct me if iam wrong.
If L1 = { anbncm | n.m >0 }L2 = { anbmcm | n, m 0}Which of these following are false?1) L1 ∩ L2 is CFL.2) L1 ∪ L2 is CFL.3) L1 and L2 are CFL.4) L1 ∩ L2 is CSL...
AnilGoudar
1.6k
views
AnilGoudar
asked
Jun 5, 2017
Theory of Computation
theory-of-computation
dcfl
closure-property
+
–
5
votes
2
answers
85
ISRO2017-77
If $L$ and $P$ are two recursively enumerable languages then they are not closed under Kleene star $L^*$ of $L$ Intersection $L \cap P$ Union $L \cup P$ Set difference
If $L$ and $P$ are two recursively enumerable languages then they are not closed underKleene star $L^*$ of $L$Intersection $L \cap P$Union $L \cup P$Set difference
sh!va
6.8k
views
sh!va
asked
May 7, 2017
Theory of Computation
isro2017
set-theory
theory-of-computation
recursive-and-recursively-enumerable-languages
closure-property
+
–
0
votes
1
answer
86
Peter Linz Exercise 4.3
Ayush Upadhyaya
237
views
Ayush Upadhyaya
asked
Mar 15, 2017
Theory of Computation
theory-of-computation
regular-language
closure-property
+
–
41
votes
6
answers
87
GATE CSE 2017 Set 2 | Question: 04
Let $L_1, L_2$ be any two context-free languages and $R$ be any regular language. Then which of the following is/are CORRECT? $L_1 \cup L_2$ is context-free $\overline{L_1}$ is context-free $L_1 - R$ is context-free $L_1 \cap L_2$ is context-free I, II and IV only I and III only II and IV only I only
Let $L_1, L_2$ be any two context-free languages and $R$ be any regular language. Then which of the following is/are CORRECT?$L_1 \cup L_2$ is context-free$\overline{L_1}...
khushtak
11.6k
views
khushtak
asked
Feb 14, 2017
Theory of Computation
gatecse-2017-set2
theory-of-computation
closure-property
+
–
2
votes
1
answer
88
Test by Bikram | Mock GATE | Test 3 | Question: 1
$X$ and $Y$ are two sets of strings from $\Sigma^*.$ Assume that $Y\subseteq X.$ Which of the following statements must ALWAYS be true for $X$and $Y?$ If $X$ is finite then $Y$ is finite. If $X$ is regular then $Y$ is regular. If $X$ is context-free, then $Y$ is context-free. I only II only III only I, II & III
$X$ and $Y$ are two sets of strings from $\Sigma^*.$ Assume that $Y\subseteq X.$Which of the following statements must ALWAYS be true for $X$and $Y?$If $X$ is finite the...
Bikram
281
views
Bikram
asked
Feb 9, 2017
Theory of Computation
tbb-mockgate-3
theory-of-computation
identify-class-language
closure-property
+
–
4
votes
0
answers
89
Are CSL, RE, Recursive languages closed under Subset operation?
Regular languages are not closed under Subset - Example anbn is subset of a*b* which is non-regular. DCFL/CFL languages are not closed under Subset - Example anbncn is subset of anbnc* which is non-cfl. Are the languages CSL,Recursive or Recursively Enumerable lanuages closed under Subset operation?
Regular languages are not closed under Subset - Example anbn is subset of a*b* which is non-regular.DCFL/CFL languages are not closed under Subset - Example anbncn is su...
yg92
2.7k
views
yg92
asked
Feb 8, 2017
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
context-sensitive
context-sensitive-languages
closure-property
+
–
0
votes
1
answer
90
Decidablity+DCFL
I) L-R where L is DCFl and R is regular. Is L-R also DCFL decidable or not??? II)If L1 is reducible to L2 and L2 is non-RE then L1 is also Non-RE??? III) If L1 is reducible to L2 and L1 is non-RE then L2 is also non-RE??
I) L-R where L is DCFl and R is regular. Is L-R also DCFL decidable or not???II)If L1 is reducible to L2 and L2 is non-RE then L1 is also Non-RE??? III) If L1 is reducibl...
Rahul Jain25
812
views
Rahul Jain25
asked
Feb 7, 2017
Theory of Computation
theory-of-computation
decidability
dcfl
closure-property
regular-language
recursive-and-recursively-enumerable-languages
+
–
Page:
« prev
1
2
3
4
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register