2013-03-06
HW 2 group 2 problem 1.
Originally Posted By: dannyR
1. To create the regular expression L', do we used the algorithm of converting a language to a DFA, then convert the DFA to a GNFA and finally to a regular expression?
L' is a language not a regular expression. For the first part of the problem come up with a map from the alphabet of L to the alphabet of L' which extends to a homomorphism of these two language. This can be done in an ad hoc manner rather than some algorithm from class.
You do not need to do anything with GNFAs for this problem. Directly give a regular expression R for L using an ad hoc method.
2. When applying the homomorphic algorithm to question 1, is R' in the homomorphic algorithm referring to the regular expression obtain from L'?
The algorithm for this part of the problem is that extracted from the proof that the regular languages are closed under homomorphic images applied to the R and h you got in the first part of the problem.
L' is a language not a regular expression. For the first part of the problem come up with a map from the alphabet of L to the alphabet of L' which extends to a homomorphism of these two language. This can be done in an ad hoc manner rather than some algorithm from class.
You do not need to do anything with GNFAs for this problem. Directly give a regular expression R for L using an ad hoc method.
2. When applying the homomorphic algorithm to question 1, is R' in the homomorphic algorithm referring to the regular expression obtain from L'?
The algorithm for this part of the problem is that extracted from the proof that the regular languages are closed under homomorphic images applied to the R and h you got in the first part of the problem.
'''Originally Posted By: dannyR'''
1. To create the regular expression L', do we used the algorithm of converting a language to a DFA, then convert the DFA to a GNFA and finally to a regular expression?<br><br>L' is a language not a regular expression. For the first part of the problem come up with a map from the alphabet of L to the alphabet of L' which extends to a homomorphism of these two language. This can be done in an ad hoc manner rather than some algorithm from class.<br>You do not need to do anything with GNFAs for this problem. Directly give a regular expression R for L using an ad hoc method.<br><br> 2. When applying the homomorphic algorithm to question 1, is R' in the homomorphic algorithm referring to the regular expression obtain from L'?<br><br>The algorithm for this part of the problem is that extracted from the proof that the regular languages are closed under homomorphic images applied to the R and h you got in the first part of the problem.
(c) 2025 Yioop - PHP Search Engine