Michael Sipser Edition 3 Exercise 5 Question 1 (Page No. 239)

admin asked Oct 17, 2019 • edited Oct 17, 2019 by Lakshman Bhaiya

164 views

See all

Please log in or register to answer this question.

Related questions

3 votes

0 answers

admin asked Oct 20, 2019

631 views

Michael Sipser Edition 3 Exercise 5 Question 36 (Page No. 242)
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$. Show that $MIN_{CFG}$ is $T-$recognizable. Show that $MIN_{CFG}$ is undecidable.

Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CF...

admin

631 views

admin asked Oct 20, 2019

0 votes

0 answers

admin asked Oct 20, 2019

455 views

Michael Sipser Edition 3 Exercise 5 Question 32 (Page No. 241)
Prove that the following two languages are undecidable. $OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$. $PREFIX-FREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefix-free}\}$.

Prove that the following two languages are undecidable.$OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$.$PREF...

admin

455 views

admin asked Oct 20, 2019

0 votes

0 answers

admin asked Oct 19, 2019

395 views

Michael Sipser Edition 3 Exercise 5 Question 21 (Page No. 240)
Let $AMBIG_{CFG} = \{\langle G \rangle \mid \text{G is an ambiguous CFG}\}$. Show that $AMBIG_{CFG}$ is undecidable. (Hint: Use a reduction from $PCP$ ... $a_{1},\dots,a_{k}$ are new terminal symbols. Prove that this reduction works.)

Let $AMBIG_{CFG} = \{\langle G \rangle \mid \text{G is an ambiguous CFG}\}$. Show that $AMBIG_{CFG}$ is undecidable. (Hint: Use a reduction from $PCP$. Given an instance...

admin

395 views

admin asked Oct 19, 2019

0 votes

0 answers

admin asked Oct 17, 2019

174 views

Michael Sipser Edition 3 Exercise 5 Question 2 (Page No. 239)
Show that $EQ_{CFG}$ is co-Turing-recognizable.

Show that $EQ_{CFG}$ is co-Turing-recognizable.

admin

174 views

admin asked Oct 17, 2019

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

Michael Sipser Edition 3 Exercise 5 Question 1 (Page No. 239)

Please log in or register to add a comment.

Please log in or register to answer this question.

0 Answers

Related questions

0 reply

Please log in or register to add a comment.

Please log in or register to answer this question.

0 Answers

Related questions

0