The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged pcp
+1
vote
0
answers
1
Ullman (TOC) Edition 3 Exercise 9.5 Question 3 (Page No. 418  419)
It is undecidable whether the complement of a CFL is also a CFL. Exercise $9.5.2$ can be used to show it is undecidable whether the complement of a CFL is regular, but that is not the same thing. To prove our initial ... Ogden's lemma to force equality in the lengths of certain substrings as in the hint to Exercise $7.2.5(b)$.
asked
Jul 26, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

89
views
ullman
theoryofcomputation
contextfreelanguages
pcp
descriptive
0
votes
0
answers
2
Ullman (TOC) Edition 3 Exercise 9.5 Question 2 (Page No. 418)
Show that the language $\overline{L_A}\cup \overline{L_B}$ is a regular language if and only if it is the set of all strings over its alphabet;i.e., if and only if the instance $(A,B)$ of PCP has no ... homomorphism, complementation and the pumping lemma for regular sets to show that $\overline{L_A}\cup \overline{L_B}$ is not regular.
asked
Jul 26, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

35
views
ullman
theoryofcomputation
regularlanguages
pcp
descriptive
0
votes
0
answers
3
Ullman (TOC) Edition 3 Exercise 9.5 Question 1 (Page No. 418)
Let $L$ be the set of (codes for) contextfree grammars $G$ such that $L(G)$ contains at least one palindrome. Show that $L$ is undecidable. Hint: Reduce PCP to $L$ by constructing, from each instance of PCP a grammar whose language contains a palindrome if and only if the PCP instance has a solution.
asked
Jul 26, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.6k
points)

12
views
ullman
theoryofcomputation
contextfreegrammars
pcp
descriptive
To see more, click for the
full list of questions
or
popular tags
.
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Contesting Answer Key Link Is Live Now
Answer keys are released for Gate2020
My Experience at IIT Madras and Some Insights
GATE Meetup at CSA IISC on February 29 as part of CSA Open Day
Make Rank Predictor Dynamic (Again?)
Follow @csegate
Recent questions tagged pcp
Recent Blog Comments
Has anyone challenge TLB question? In GO all the...
challenge for the regular expression question
And for cs 43, I have this doubt (reposting...
For cs 16 refer to Arjun sir answer, O(nlogn) in...
I think in that question then have taken 1...
50,833
questions
57,705
answers
199,411
comments
107,565
users