menu
search
Log In
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

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Michael Sipser Edition 3 Exercise 4 Question 22 (Page No. 212)

0 votes
152 views
Let $PREFIX-FREE_{REX} = \{\langle R \rangle \mid \text{R is a regular expression and L(R) is prefix-free}\}$. Show that $PREFIX FREE_{REX}$ is decidable. Why does a similar approach fail to show that $PREFIX-FREE_{CFG}$ is decidable?
in Theory of Computation
edited by 152 views

Please log in or register to answer this question.

← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →

Related questions

0 votes
0 answers
1
111 views
Michael Sipser Edition 3 Exercise 4 Question 2 (Page No. 211)
Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.
Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.
asked Oct 16, 2019 in Theory of Computation Lakshman Patel RJIT 111 views
0 votes
0 answers
2
141 views
Michael Sipser Edition 3 Exercise 4 Question 31 (Page No. 212)
Say that a variable $A$ in $CFL\: G$ is usable if it appears in some derivation of some string $w \in G$. Given a $CFG\: G$ and a variable $A$, consider the problem of testing whether $A$ is usable. Formulate this problem as a language and show that it is decidable.
Say that a variable $A$ in $CFL\: G$ is usable if it appears in some derivation of some string $w \in G$. Given a $CFG\: G$ and a variable $A$, consider the problem of testing whether $A$ is usable. Formulate this problem as a language and show that it is decidable.
asked Oct 17, 2019 in Theory of Computation Lakshman Patel RJIT 141 views
0 votes
0 answers
3
59 views
Michael Sipser Edition 3 Exercise 4 Question 30 (Page No. 212)
Let $A$ be a Turing-recognizable language consisting of descriptions of Turing machines, $\{ \langle M_{1}\rangle,\langle M_{2}\rangle,\dots\}$, where every $M_{i}$ is a decider. Prove that some decidable language $D$ is not ... $A$. (Hint: You may find it helpful to consider an enumerator for $A$.)
Let $A$ be a Turing-recognizable language consisting of descriptions of Turing machines, $\{ \langle M_{1}\rangle,\langle M_{2}\rangle,\dots\}$, where every $M_{i}$ is a decider. Prove that some decidable language $D$ is not decided by any decider $M_{i}$ whose description appears in $A$. (Hint: You may find it helpful to consider an enumerator for $A$.)
asked Oct 17, 2019 in Theory of Computation Lakshman Patel RJIT 59 views
0 votes
0 answers
4
72 views
Michael Sipser Edition 3 Exercise 4 Question 29 (Page No. 212)
Let $C_{CFG} = \{\langle G, k \rangle \mid \text{ G is a CFG and L(G) contains exactly $k$ strings where $k \geq 0$ or $k = \infty$}\}$. Show that $C_{CFG}$ is decidable.
Let $C_{CFG} = \{\langle G, k \rangle \mid \text{ G is a CFG and L(G) contains exactly $k$ strings where $k \geq 0$ or $k = \infty$}\}$. Show that $C_{CFG}$ is decidable.
asked Oct 17, 2019 in Theory of Computation Lakshman Patel RJIT 72 views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...