Skip to main content
Computer Science

Return to Answer

deleted 4 characters in body
Source Link
dkaeae
dkaeae
  • 5k
  • 1
  • 16
  • 31

Your answer is also correct. Regular languages do not have unique regexes. For example, $0^\ast$, $0^\ast 0^\ast$, and $0^\ast 0^\ast 0^\ast$ are different regexes, but all representing the language of strings containing only zeroes.

The problem of deciding whether two regexes are equivalent (i.e., whether they represent the same language) is actually very hard, as mentioned in this answer. (Spoiler: it is $\mathbf{PSPACE}$-complete.)

As to your other question (regarding a CFG for the language), here is a hint: divide and conquer. Split the regex in multiple "chunks" and try to generate each chunk separately, then pack everything together with the grammar's start symbol.

Your answer is also correct. Regular languages do not have unique regexes. For example, $0^\ast$, $0^\ast 0^\ast$, and $0^\ast 0^\ast 0^\ast$ are different regexes, but all representing the language of strings containing only zeroes.

The problem of deciding whether two regexes are equivalent (i.e., whether they represent the same language) is actually very hard, as mentioned in this answer. (Spoiler: it is $\mathbf{PSPACE}$-complete.)

As to your other question (regarding a CFG for the language), here is a hint: divide and conquer. Split the regex in multiple "chunks" and try to generate each chunk separately, then pack everything together with the grammar's start symbol.

Your answer is also correct. Regular languages do not have unique regexes. For example, $0^\ast$, $0^\ast 0^\ast$, and $0^\ast 0^\ast 0^\ast$ are different regexes, all representing the language of strings containing only zeroes.

The problem of deciding whether two regexes are equivalent (i.e., whether they represent the same language) is actually very hard, as mentioned in this answer. (Spoiler: it is $\mathbf{PSPACE}$-complete.)

As to your other question (regarding a CFG for the language), here is a hint: divide and conquer. Split the regex in multiple "chunks" and try to generate each chunk separately, then pack everything together with the grammar's start symbol.

Source Link
dkaeae
dkaeae
  • 5k
  • 1
  • 16
  • 31

Your answer is also correct. Regular languages do not have unique regexes. For example, $0^\ast$, $0^\ast 0^\ast$, and $0^\ast 0^\ast 0^\ast$ are different regexes, but all representing the language of strings containing only zeroes.

The problem of deciding whether two regexes are equivalent (i.e., whether they represent the same language) is actually very hard, as mentioned in this answer. (Spoiler: it is $\mathbf{PSPACE}$-complete.)

As to your other question (regarding a CFG for the language), here is a hint: divide and conquer. Split the regex in multiple "chunks" and try to generate each chunk separately, then pack everything together with the grammar's start symbol.