Skip to main content
Computer Science

Return to Question

There was a typo in the book's name.
Source Link
edit approved Jun 2, 2020 at 15:10
Utkan Gezer
edit approved Jun 2, 2020 at 15:10
Utkan Gezer
  • 105
  • 3

How could I prove that the following language is decidable?

$\{\langle G\rangle \mid G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$

P.S. It's the problem 4.15 of the third edition of the "Introduction to the ThoeryTheory of Computation" by Michael Sipser.

How could I prove that the following language is decidable?

$\{\langle G\rangle \mid G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$

P.S. It's the problem 4.15 of the third edition of the "Introduction to the Thoery of Computation" by Michael Sipser.

How could I prove that the following language is decidable?

$\{\langle G\rangle \mid G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$

P.S. It's the problem 4.15 of the third edition of the "Introduction to the Theory of Computation" by Michael Sipser.

improved title; added related tags
Source Link
edit approved Jun 5, 2018 at 14:32
xskxzr
edit approved Jun 5, 2018 at 14:32
xskxzr
  • 7.6k
  • 5
  • 23
  • 47

Decidability of the $1^* \subseteq CFG$determining whether a context-free grammar generates all strings in 1*

How could be provedI prove that the following language is decidable?

$\{\langle G\rangle|G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$$\{\langle G\rangle \mid G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$

P.S. It's the problem 4.15 of the third edition of the "Introduction to the Thoery of Computation" by Michael Sipser.

Decidability of the $1^* \subseteq CFG$

How could be proved that the following language is decidable?

$\{\langle G\rangle|G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$

P.S. It's the problem 4.15 of the third edition of the "Introduction to the Thoery of Computation" by Michael Sipser.

Decidability of determining whether a context-free grammar generates all strings in 1*

How could I prove that the following language is decidable?

$\{\langle G\rangle \mid G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$

P.S. It's the problem 4.15 of the third edition of the "Introduction to the Thoery of Computation" by Michael Sipser.

Source Link
javadr
javadr
  • 141
  • 1
  • 5

Decidability of the $1^* \subseteq CFG$

How could be proved that the following language is decidable?

$\{\langle G\rangle|G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$

P.S. It's the problem 4.15 of the third edition of the "Introduction to the Thoery of Computation" by Michael Sipser.