MEMORANDUM *

Petitioner Douglas Winston appeals the summary dismissal of his petition for a writ of habeas corpus. Winston argues that the California state regulations governing parole suitability determinations violate his due process rights because they rely upon unconstitutionally vague criteria. Because the petitioner has properly alleged that he has fully exhausted his claims in state court and the vagueness allegations contained in his petition for a writ of habeas corpus are nonfrivolous in nature, we reverse the decision of the district court.

I

In order for a state petitioner to obtain federal habeas relief, he must “exhaust the remedies available in state court.” Lounsbury v. Thompson, 374 F.3d 785, 787 (9th Cir. 2004) (citing 28 U.S.C. § 2254(b)(1); Peterson v. Lampert, 319 F.3d 1153, 1155 (9th Cir. 2003) (en banc)). In Winston’s petition for a writ of habeas corpus, he alleges that all the grounds he states for relief have been exhausted before California courts. The state did not contest this assertion of exhaustion before the district court, and nothing exists in the record before this court indicating that Winston did not comply with this requirement. Rule 5 of the Rules Governing Habeas Corpus Cases Under § 2254 requires that the state’s answer to Winston’s habeas petition “shall state whether the petitioner has exhausted his state remedies.” Because the state has yet to provide this answer to Winston’s habeas petition, at this stage of the proceedings his allegations regarding exhaustion in California courts are sufficient. If it turns out that there are facts relevant to exhaustion *804which are disputed by the state’s answer, at that point it will become an evidentiary question to be adjudicated before the district court.

II

The district court summarily dismissed Winston’s petition for a writ of habeas corpus. Under Rule 4 of the Rules Governing Habeas Corpus Cases Under § 2254, summary dismissal by the district court is only appropriate when “it plainly appears from the face of the petition and any exhibits annexed to it that the petitioner is not entitled to relief....” We have explained that “[sjummary dismissal is appropriate only where the allegations in the petition are ‘vague [or] conclusory or ‘palpably incredible’ or ‘patently frivolous or false.’ ” Hendricks v. Vasquez, 908 F.2d 490, 491 (9th Cir. 1990) (quoting Blackledge v. Allison, 431 U.S. 63, 75-76, 97 S.Ct. 1621, 52 L.Ed.2d 136 (1977)) (additional citations omitted).

Here, Winston alleges that California state regulations governing parole suitability determinations that contain guiding language such as “especially heinous, atrocious, or cruel manner” are unconstitutionally vague. See 15 Cal. Admin. Code § 2402(a). This allegation cannot be characterized as so obviously frivolous or false to allow for summary dismissal. This court has recently held that “Section 3041 of the California Penal Code creates in every inmate a cognizable liberty interest in parole which is protected by the procedural safeguards of the Due Process Clause.... The liberty interest is created, not upon the grant of a parole date, but upon the incarceration of the inmate.” Biggs v. Terhune, 334 F.3d 910, 914-15 (9th Cir. 2003) (citations omitted). Winston’s claim that the statutory language guiding parole decisions is vague clearly implicates his rights under constitutional due process. Determining whether or not this language is unconstitutionally vague probably requires that the regulations be evaluated as they have been applied to Appellant Winston. See Maynard v. Cartwright, 486 U.S. 356, 361, 108 S.Ct. 1853, 100 L.Ed.2d 372 (1988) (“Vagueness challenges to statutes not threatening First Amendment interests are examined in light of the facts of the case at hand; the statute is judged on an as-applied basis.”). Because transcripts have not yet been filed and the facts of Winston’s case have not been fully developed, it is not possible to determine the validity of Winston’s vagueness challenge. Thus, summary dismissal of Winston’s plausible claim on this incomplete record is inappropriate. We reverse the district court’s dismissal under Rule 4 and remand for further proceedings consistent with this memorandum.

REVERSED and REMANDED.