Regular expressions are a precise and succinct notation for describing languages.
For regular expressions, there are few symbal that can be eazily defined.
"+" means "or"
if two letters are together then they are listed in order
"*" means can be none or repeat any times.
"()"means the formula inside should be consider first.
Examples:
1* will be a binary string with only 1s or empty string
1+0 will be 1 or 0
(10)+(1+0) will be 10 or 1 or 0
There are Precedence rules for reducing the number of parentheses used.
A regular question will be devise a regular expressions R for a set L and prove it.
Questino:Let L be a set of binary string start with 0 and end with 0.Devise a regular expression, R that denotes L, and prove that your regular expression is correct.
For doing this kind of question, we need to find several elements in the set first.
we know that empty string is not in the set cause it doesnt has a number 0.
so the first cases will be 0 and others can be 00 010 000 0110.
So we know that expect for the first cases others will be 0+any binary string(include empty string)+0 (+ means plus here)
So the first part of the R will be 0+.
The another part will be 0(0+1)*0 as (0+1)* represents any binary string.
So R=0+0(0+1)*0
Then we have to prove that for any x ∈L, if and only if x∈L(R)
which means L=L(R)
we need to prove that in two ways that
L belongs to L(R) and L(R) belongs to L.
Well, I still dont know it clearly how to do it in correct way for this step. May have to learn it in next lecture.
没有评论:
发表评论