3 replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/ edited Apr 13 '17 at 12:48 This language was already considered by the same OP in another question http://cs.stackexchange.com/questions/24746Build a regular expression to define a regular language. But then, posters are told not to ask two questions in the same post. I already answeredanswered that a simple method is to consider the regular languages defined by conditions 1 and 2, $$1a(1+a+b)^*$$, and by conditions 1 and 3, $$(1+a+b)^*aa(1+a+b)^*$$. You take the FA for them, both having 3 states (4 if you count a dead state), and construct the FA for the intersection. Which is quite easy, and gives a five-states automaton (6 states if you count a dead state). From that FA you can get a regular expression for the language, which is $$1(a+a(1+a+b)^*a)a(1+a+b)^*$$. But you can also get a regular grammar: $$S \rightarrow 1T$$ $$T \rightarrow aX \mid aY$$ $$X \rightarrow 1X \mid aX \mid bX \mid aY$$ $$Y \rightarrow a \mid aZ$$ $$Z \rightarrow 1 \mid a \mid b \mid 1Z \mid aZ \mid bZ$$ which derives directly from the automaton. In more details: Why do it as I did above? Proving that a regular expression defines the language specified by a set of such conditions can be long and tedious. The same is true for a grammar or an automaton. This is why the proper way of answering such a question is to find a systematic way of building the desired result from elementary components for which things are obvious to prove. Here, as I had already answeredanswered, elementary components are the regular languages defined respectively by conditions 1 and 2: $$1a(1+a+b)^∗$$ ; by conditions 1 and 3: $$(1+a+b)^∗aa(1+a+b)^∗$$ . For each of these 2 languages, it is easy to find the regular expression (above) or to give a regular grammar or a finite-state automaton (FA). Each has a 3 states FA that recognizes it (4 states including a dead state). To get a FA for the language meeting all three conditions, you only have to get the intersection of these two languages. There is a standard cross-product construction for building a FA recognizing the intersection of two regular languages. This construction is easy to apply by hand in our example. It produce a 5 states FA for the language defined by all three conditions (or a 6 states FA, including a dead state). From this last FA, it is easy to build either the regular expression or the regular grammar given above. Since the answer was built in a systematic way using well known techniques (that have been proved correct long ago), there is no need to prove that the resulting regular expression, grammar or FA are correct. Barring of course mistakes in the use of the constructions ... but then, you can also make mistakes in proofs. I added the precision about dead states so that no one gets confused. But, except for some constructions, it is often simpler just to omit dead states and transitions leading to them. This language was already considered by the same OP in another question http://cs.stackexchange.com/questions/24746. But then, posters are told not to ask two questions in the same post. I already answered that a simple method is to consider the regular languages defined by conditions 1 and 2, $$1a(1+a+b)^*$$, and by conditions 1 and 3, $$(1+a+b)^*aa(1+a+b)^*$$. You take the FA for them, both having 3 states (4 if you count a dead state), and construct the FA for the intersection. Which is quite easy, and gives a five-states automaton (6 states if you count a dead state). From that FA you can get a regular expression for the language, which is $$1(a+a(1+a+b)^*a)a(1+a+b)^*$$. But you can also get a regular grammar: $$S \rightarrow 1T$$ $$T \rightarrow aX \mid aY$$ $$X \rightarrow 1X \mid aX \mid bX \mid aY$$ $$Y \rightarrow a \mid aZ$$ $$Z \rightarrow 1 \mid a \mid b \mid 1Z \mid aZ \mid bZ$$ which derives directly from the automaton. In more details: Why do it as I did above? Proving that a regular expression defines the language specified by a set of such conditions can be long and tedious. The same is true for a grammar or an automaton. This is why the proper way of answering such a question is to find a systematic way of building the desired result from elementary components for which things are obvious to prove. Here, as I had already answered, elementary components are the regular languages defined respectively by conditions 1 and 2: $$1a(1+a+b)^∗$$ ; by conditions 1 and 3: $$(1+a+b)^∗aa(1+a+b)^∗$$ . For each of these 2 languages, it is easy to find the regular expression (above) or to give a regular grammar or a finite-state automaton (FA). Each has a 3 states FA that recognizes it (4 states including a dead state). To get a FA for the language meeting all three conditions, you only have to get the intersection of these two languages. There is a standard cross-product construction for building a FA recognizing the intersection of two regular languages. This construction is easy to apply by hand in our example. It produce a 5 states FA for the language defined by all three conditions (or a 6 states FA, including a dead state). From this last FA, it is easy to build either the regular expression or the regular grammar given above. Since the answer was built in a systematic way using well known techniques (that have been proved correct long ago), there is no need to prove that the resulting regular expression, grammar or FA are correct. Barring of course mistakes in the use of the constructions ... but then, you can also make mistakes in proofs. I added the precision about dead states so that no one gets confused. But, except for some constructions, it is often simpler just to omit dead states and transitions leading to them. This language was already considered by the same OP in another question Build a regular expression to define a regular language. But then, posters are told not to ask two questions in the same post. I already answered that a simple method is to consider the regular languages defined by conditions 1 and 2, $$1a(1+a+b)^*$$, and by conditions 1 and 3, $$(1+a+b)^*aa(1+a+b)^*$$. You take the FA for them, both having 3 states (4 if you count a dead state), and construct the FA for the intersection. Which is quite easy, and gives a five-states automaton (6 states if you count a dead state). From that FA you can get a regular expression for the language, which is $$1(a+a(1+a+b)^*a)a(1+a+b)^*$$. But you can also get a regular grammar: $$S \rightarrow 1T$$ $$T \rightarrow aX \mid aY$$ $$X \rightarrow 1X \mid aX \mid bX \mid aY$$ $$Y \rightarrow a \mid aZ$$ $$Z \rightarrow 1 \mid a \mid b \mid 1Z \mid aZ \mid bZ$$ which derives directly from the automaton. In more details: Why do it as I did above? Proving that a regular expression defines the language specified by a set of such conditions can be long and tedious. The same is true for a grammar or an automaton. This is why the proper way of answering such a question is to find a systematic way of building the desired result from elementary components for which things are obvious to prove. Here, as I had already answered, elementary components are the regular languages defined respectively by conditions 1 and 2: $$1a(1+a+b)^∗$$ ; by conditions 1 and 3: $$(1+a+b)^∗aa(1+a+b)^∗$$ . For each of these 2 languages, it is easy to find the regular expression (above) or to give a regular grammar or a finite-state automaton (FA). Each has a 3 states FA that recognizes it (4 states including a dead state). To get a FA for the language meeting all three conditions, you only have to get the intersection of these two languages. There is a standard cross-product construction for building a FA recognizing the intersection of two regular languages. This construction is easy to apply by hand in our example. It produce a 5 states FA for the language defined by all three conditions (or a 6 states FA, including a dead state). From this last FA, it is easy to build either the regular expression or the regular grammar given above. Since the answer was built in a systematic way using well known techniques (that have been proved correct long ago), there is no need to prove that the resulting regular expression, grammar or FA are correct. Barring of course mistakes in the use of the constructions ... but then, you can also make mistakes in proofs. I added the precision about dead states so that no one gets confused. But, except for some constructions, it is often simpler just to omit dead states and transitions leading to them. 2 Explained how to find such answers. edited May 17 '14 at 8:14 babou 17.6k2727 silver badges6969 bronze badges This language was already considered by the same OP in another question http://cs.stackexchange.com/questions/24746. But then, posters are told not to ask two questions in the same post. I already answered that a simple method is to consider the regular languages defined by conditions 1 and 2, $$1a(1+a+b)^*$$, and by conditions 1 and 3, $$(1+a+b)^*aa(1+a+b)^*$$. You take the FA for them, both having 3 states (4 if you count a dead state), and construct the FA for the intersection. Which is quite easy, and gives a five-states automaton (6 states if you count a dead state). From that FA you can get a regular expression for the language, which is $$1(a+a(1+a+b)^*a)a(1+a+b)^*$$. But you can also get a regular grammar: $$S \rightarrow 1T$$ $$T \rightarrow aX \mid aY$$ $$X \rightarrow 1X \mid aX \mid bX \mid aY$$ $$Y \rightarrow a \mid aZ$$ $$Z \rightarrow 1 \mid a \mid b \mid 1Z \mid aZ \mid bZ$$ which derives directly from the automaton. In more details: Why do it as I did above? Proving that a regular expression defines the language specified by a set of such conditions can be long and tedious. The same is true for a grammar or an automaton. This is why the proper way of answering such a question is to find a systematic way of building the desired result from elementary components for which things are obvious to prove. Here, as I had already answered, elementary components are the regular languages defined respectively by conditions 1 and 2: $$1a(1+a+b)^∗$$ ; by conditions 1 and 3: $$(1+a+b)^∗aa(1+a+b)^∗$$ . For each of these 2 languages, it is easy to find the regular expression (above) or to give a regular grammar or a finite-state automaton (FA). Each has a 3 states FA that recognizes it (4 states including a dead state). To get a FA for the language meeting all three conditions, you only have to get the intersection of these two languages. There is a standard cross-product construction for building a FA recognizing the intersection of two regular languages. This construction is easy to apply by hand in our example. It produce a 5 states FA for the language defined by all three conditions (or a 6 states FA, including a dead state). From this last FA, it is easy to build either the regular expression or the regular grammar given above. Since the answer was built in a systematic way using well known techniques (that have been proved correct long ago), there is no need to prove that the resulting regular expression, grammar or FA are correct. Barring of course mistakes in the use of the constructions ... but then, you can also make mistakes in proofs. I added the precision about dead states so that no one gets confused. But, except for some constructions, it is often simpler just to omit dead states and transitions leading to them. This language was already considered by the same OP in another question http://cs.stackexchange.com/questions/24746 I already answered that a simple method is to consider the regular languages defined by conditions 1 and 2, $$1a(1+a+b)^*$$, and by conditions 1 and 3, $$(1+a+b)^*aa(1+a+b)^*$$. You take the FA for them, both having 3 states, and construct the FA for the intersection. Which is quite easy, and gives a five-states automaton. From that FA you can get a regular expression for the language, which is $$1(a+a(1+a+b)^*a)a(1+a+b)^*$$. But you can also get a regular grammar: $$S \rightarrow 1T$$ $$T \rightarrow aX \mid aY$$ $$X \rightarrow 1X \mid aX \mid bX \mid aY$$ $$Y \rightarrow a \mid aZ$$ $$Z \rightarrow 1 \mid a \mid b \mid 1Z \mid aZ \mid bZ$$ which derives directly from the automaton. This language was already considered by the same OP in another question http://cs.stackexchange.com/questions/24746. But then, posters are told not to ask two questions in the same post. I already answered that a simple method is to consider the regular languages defined by conditions 1 and 2, $$1a(1+a+b)^*$$, and by conditions 1 and 3, $$(1+a+b)^*aa(1+a+b)^*$$. You take the FA for them, both having 3 states (4 if you count a dead state), and construct the FA for the intersection. Which is quite easy, and gives a five-states automaton (6 states if you count a dead state). From that FA you can get a regular expression for the language, which is $$1(a+a(1+a+b)^*a)a(1+a+b)^*$$. But you can also get a regular grammar: $$S \rightarrow 1T$$ $$T \rightarrow aX \mid aY$$ $$X \rightarrow 1X \mid aX \mid bX \mid aY$$ $$Y \rightarrow a \mid aZ$$ $$Z \rightarrow 1 \mid a \mid b \mid 1Z \mid aZ \mid bZ$$ which derives directly from the automaton. In more details: Why do it as I did above? Proving that a regular expression defines the language specified by a set of such conditions can be long and tedious. The same is true for a grammar or an automaton. This is why the proper way of answering such a question is to find a systematic way of building the desired result from elementary components for which things are obvious to prove. Here, as I had already answered, elementary components are the regular languages defined respectively by conditions 1 and 2: $$1a(1+a+b)^∗$$ ; by conditions 1 and 3: $$(1+a+b)^∗aa(1+a+b)^∗$$ . For each of these 2 languages, it is easy to find the regular expression (above) or to give a regular grammar or a finite-state automaton (FA). Each has a 3 states FA that recognizes it (4 states including a dead state). To get a FA for the language meeting all three conditions, you only have to get the intersection of these two languages. There is a standard cross-product construction for building a FA recognizing the intersection of two regular languages. This construction is easy to apply by hand in our example. It produce a 5 states FA for the language defined by all three conditions (or a 6 states FA, including a dead state). From this last FA, it is easy to build either the regular expression or the regular grammar given above. Since the answer was built in a systematic way using well known techniques (that have been proved correct long ago), there is no need to prove that the resulting regular expression, grammar or FA are correct. Barring of course mistakes in the use of the constructions ... but then, you can also make mistakes in proofs. I added the precision about dead states so that no one gets confused. But, except for some constructions, it is often simpler just to omit dead states and transitions leading to them. 1 answered May 16 '14 at 20:00 babou 17.6k2727 silver badges6969 bronze badges This language was already considered by the same OP in another question http://cs.stackexchange.com/questions/24746 I already answered that a simple method is to consider the regular languages defined by conditions 1 and 2, $$1a(1+a+b)^*$$, and by conditions 1 and 3, $$(1+a+b)^*aa(1+a+b)^*$$. You take the FA for them, both having 3 states, and construct the FA for the intersection. Which is quite easy, and gives a five-states automaton. From that FA you can get a regular expression for the language, which is $$1(a+a(1+a+b)^*a)a(1+a+b)^*$$. But you can also get a regular grammar: $$S \rightarrow 1T$$ $$T \rightarrow aX \mid aY$$ $$X \rightarrow 1X \mid aX \mid bX \mid aY$$ $$Y \rightarrow a \mid aZ$$ $$Z \rightarrow 1 \mid a \mid b \mid 1Z \mid aZ \mid bZ$$ which derives directly from the automaton.