-3
$\begingroup$

This is our alphabet: $\{0,1,2\}$

And lets say I have two regular expressions:

Regular expression 1. $(1|22|0)^* (2|0)^*$

Regular expression 2. $(0|1)^* (1|20|1)^*$

How can I give three words each over the alphabet such that they are:

  • in both languages
  • in the first language but not in the second language
  • not in the first language but are in the second language
  • not in either of the languages
$\endgroup$

closed as unclear what you're asking by David Richerby, Evil, Juho, Rick Decker, Tom van der Zanden Nov 1 '16 at 13:27

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ How about trying a few words captured by each of the regular expressions, and take it from there? $\endgroup$ – Yuval Filmus Oct 23 '16 at 22:14
  • 4
    $\begingroup$ What have you tried? Where did you get stuck? If this is a homework it will be harmful to give you the words, so please refine your question and show your steps. BTW the first RE has no "0" - where does this hint help? $\endgroup$ – Evil Oct 23 '16 at 22:17
  • $\begingroup$ @Evil The regular expressions are different to the ones that are set on my homework, I changed the numbers around because I don't want to be kicked out for plagiarism. And the thing is, I have absolutely no idea how to approach this problem. I've only been learning about regular expressions for 2 weeks $\endgroup$ – fs2ly Oct 23 '16 at 22:20
  • 1
    $\begingroup$ 1) Changing the alphabet does make this not plagiarism. Don't cheat! 2) Trying a few words is not hard, and takes less than two weeks of exposure to the concept. 3) If you want to go the arduous but sure way, transform the regular expressions and use the closure property constructions for finite automata to get automata for union, both differences, and the complement of the union. Then read off words from the automata. $\endgroup$ – Raphael Oct 23 '16 at 22:33
  • $\begingroup$ @Raphael I feel so much pressure. I know that I need to find the union and intersection but I'm not sure how. I don't think I'm cheating, I don't want to cheat because I won't learn anything... I just want to be taught how the steps/formula work so I can solve problems like this. $\endgroup$ – fs2ly Oct 23 '16 at 22:40
0
$\begingroup$

I've worked out how to tackle my problem.

The way I did it was by converting the regular expressions into DFA's and then visually following the DFA to find words that are in both languages, in the first language but not the second, in the second language but not the first and finally, not in both of the languages.

The alphabet is {0,1,2}

Regular expression 1. (1|22|0)∗(2|0)∗

Regular expression 2. (0|1)∗(1|20|1)∗

Give three words each over the alphabet such that they are:

  • in both languages

  • in the first language but not in the second language

  • not in the first language but are in the second language

  • not in either of the languages

Here is my solution:

Step 1:

Convert the regular expressions into automatons.

(Unfortunately, I can't post the images directly to stackoverflow because I do not have enough reputation points. Instead, click the images below to see the DFA's).

DFA of the first regular expression: https://s17.postimg.org/9rbdmk94f/automaton_1.png

DFA of the second regular expression: https://s18.postimg.org/3jtyzdesp/automaton_2.png

Step 2:

Follow the transitions of the DFA to check if the DFA accepts or rejects the word. If it accepts the word, it is in the language, if it rejects the word, it is not in the language.

Answer to question

Three words over the alphabet which are in both of the languages:

1) 00

2) 10101

3) 2020

Three words over the alphabet which are in the first language but not the second:

1) 2222

2) 0102

3) 22

Three words over the alphabet which are in the second language but not the first:

1) 01201

2) 2011

3) 1011201

Three words over the alphabet which are not in both of the languages:

1) 2221

2) 1021

3) 011001121

The problem with this method is if your regular expression is really long and complex, then it might be difficult to draw out a DFA and visually find words that are in and are not in the language. But this method will help if your regular expression is fairly short and simple.

I hope my answer was of help to anyone else who is interested to tackle similar problems.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.