formal languages - Regex create a expression solving the following pattern -


this part of university optional homework , kinda struggling bit.

the pattern solve isn't hard honest don't our heads around it, create expression has alphabet {a,b,c} contains @ least 1 a , 1 b.

current 2 approaches

(a|b|c)*a(a|b|c)*b(a|b|c)* or (a|b|c)(a|b)(a|b|c)*(a|b)(a|b|c)*

but both of these have flaws first 1 wouldnt allow ccbacc second 1 allow ccaacc.

greetings

there can 2 rules produce requirement, 1 a before b:

s₁ → [abc]* [abc]* b [abc]* 

the other b before a

s₂ → [abc]* b [abc]* [abc]* 

now combine them using alternative operator,

s → s₁ | s₂   = [abc]* [abc]* b [abc]* | [abc]* b [abc]* [abc]* 

this can simplified using rule ab|ac = a(b|c) , ac|bc = (a|b)c:

s → [abc]* (a [abc]* b | b [abc]* a) [abc]* 

i assume homework deals formal language. in real programming, use indexof or similar functions find out if string contains a , b. regex heavy task.


Comments

Popular posts from this blog

ios - RestKit 0.20 — CoreData: error: Failed to call designated initializer on NSManagedObject class (again) -

laravel - PDOException in Connector.php line 55: SQLSTATE[HY000] [1045] Access denied for user 'root'@'localhost' (using password: YES) -

java - Digest auth with Spring Security using javaconfig -