0% found this document useful (0 votes)
6 views1 page

Regular Expressions and DFA Tutorial

The document is a tutorial from the Thapar Institute of Engineering and Technology's Computer Science and Engineering Department. It contains a series of exercises requiring the creation of regular expressions (R.E.) for various languages defined over specific alphabets. Additionally, it includes a task to design a deterministic finite automaton (DFA) for the problems presented.
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
6 views1 page

Regular Expressions and DFA Tutorial

The document is a tutorial from the Thapar Institute of Engineering and Technology's Computer Science and Engineering Department. It contains a series of exercises requiring the creation of regular expressions (R.E.) for various languages defined over specific alphabets. Additionally, it includes a task to design a deterministic finite automaton (DFA) for the problems presented.
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Tutorial 2

Thapar Institute of Engineering and Technology Patiala

Computer Science and Engineering Department (CSED)


1. Write down a R.E. over {0, 1} such that no. of 1’s are divisible by 4.
2. Write down a regular expression for language L over {a, b, c} such that every string in L
contains a substring ccc.
3. Write down a R.E. for the language L={w: | w | mod 5=0}, w  (a, b) }
4. Write down a R.E. over alphabet  = {a, b, c} containing at least one a and at least one b.
5. Write the Regular expression for the language of all even length strings defined over
 = {a, b}.
6. Write the Regular expression for the language of all even length strings defined over
 = {a, b}.
7. Write the Regular expression for the language L = {a nb m | n, m  1} over  = {a, b}.
8. Write the Regular expression for the language L = {a nb m | n, m  0} over  = {a, b}.
9. Write down a R.E. over {0, 1} whose fifth symbol from the right end is 1.

9. Design the DFA for the problem given in Q1-8.

Common questions

Powered by AI

The regular expression '(a(ab)*b)*' describes the language {a^n b^m : n ≥ 1, m ≥ 1}. This expression ensures there is at least one 'a' followed by at least one 'b' due to the mandatory 'a' initial position and subsequent pattern enforcement post repetition.

The regular expression for the language where the length is a multiple of 5 can be expressed as '((a|b){5})*'. This expression works by repeating any string of exactly five characters drawn from the alphabet {a, b}, thereby guaranteeing that the total length is always a multiple of five.

The design differences of a DFA handling alphabets {a, b} versus {0, 1} arise from the properties associated with specific character sequences. For strings where certain substrings or placements are critical, such as ensuring a position-specific character, states are in sequence aligned to positional requisites. Control transitions enforce the correct sequence or positional reading, differing based on inherent alphabetical roles or potential combinations adhered by state machine continuity or divergence concerning the given problem.

The regular expression '(0|1)*(1) (0|1){4}' ensures that the fifth symbol from the right is '1'. The logic involves allowing any sequence of '0's or '1's, followed by a '1', and then exactly four further symbols of any type. This expression directly positions '1' temporally from the string's end.

A DFA for the expression where '1's are divisible by 4 would have states representing counts of '1's modulo 4. Transitions on '1' increment the count state, proceeding full cycle upon reaching the fourth, creating cycles that ensure divisibility by four. For strings with lengths multiple of 5, states track the modulo 5 of the string length, with transitions upon character reading preserving this. An accepting state is reached when the total length modulo equals zero, ensuring the length is a '5n'.

A regular expression ensuring each string contains at least one 'a' and one 'b' over the alphabet {a, b, c} can be derived as such: '(c*b*c*a+c*a*c*b+...)*', where the pattern ensures all combinations start with or result in having at least one 'a' and 'b'. This uses the properties of optional motifs interspersed with mandatory characters, crafting a structure where absence of either 'a' or 'b' becomes impossible.

A regular expression over {0, 1} such that the number of '1's is divisible by 4 can be constructed by considering groups of four '1's interspersed with any number of '0's or no '0' at all. The expression '(0*10*10*10*10*)*' represents a set of strings where each '1' is isolated by any number of '0's. For each sequence for '1's, this guarantees the divisibility condition.

The regular expression for even-length strings over {a, b} is '((a|b)(a|b))*'. This uses the idea that an even-length string can be constructed by concatenating any pair from the alphabet (a or b) repeatedly. Each use of '(a|b)(a|b)' ensures the addition of exactly two characters, maintaining evenness.

A regular expression to start with 'ab' is structured by appending '(ab)' at the begining followed by '(a|b)*'. This ensures the initial sequence 'ab' is mandatory, with flexibility following for any length or combination of 'a' and 'b', maintaining the initial required sequence.

To ensure that the substring 'ccc' appears in every string of the language L, a regular expression can be designed as '(a|b|cc)*ccc(a|b|cc)*'. This expression allows any combination of the characters 'a', 'b', and 'cc' on either side of 'ccc', but crucially includes the 'ccc' substring once in every string, fulfilling the requirement that each string in L contains 'ccc'.

You might also like