Computer Science: Regular languages, Regular expressions, and Finite Automata I

Question

Computer Science: Regular languages, Regular expressions, and Finite Automata

I do not understand how to do any of these problems. My professor has given us the answers. Please provide an extremely detailed dumbed down explanation so I can understand how to do these type of problems. If there are other solutions, please explain. Thanks

1a) L is the language of odd length strings of zeroes. Give a regex for L.

Answer: 0(00)*

1b) L is the language of all strings over alphabet {0,1} where every 1 has an adjacent 1.

Answer: (0 | 111*)* or (0|11+)*

1c) L is the language of odd decimal integers greater than 0. Give a regex for L.

Answer: [1-9][0-9]* (1|3|5|7|9)|1|3|5|7|9

Explanation / Answer

1a) L is the language of odd length strings of zeroes

Odd length strings of zeroes means the number of zeros count is odd.

Odd length strings of zeroes are {0,000,00000,.........}

(00)* : It means it produce zeors are 0,2,4,6,8,10.....

So the number of 0's produced by (00)* is 0 or multiles of 2 zero's

0(00)* : Here first 1 zero produced by first position 0 after that (00)* 0 or multiles of 2 zero's

(00)* produces no zeros then 0(00)* is 0

(00)* produces two zeros then 0(00)* is 000

(00)* produces three zeros then 0(00)* is 00000

(00)* produces n zeros then 0(00)* is 0+(n zeros where n is always even)

Therefore 0(00)* always produces odd length strings of zeroes.

1b)

every 1 has an adjacent 1 means every 1 preceeded by 1 or succeded by 1 or preceeded and succeded by 1.

(0 | 111*)*

111* : First two1's produce 11 and 1* produces zero or more number of 1's.

so it produce 11 or 111 or 1111 or 11111.......

(0 | 111*) : It produces 0 or 111*

(0 | 111*)* : It produces zero or more number of

1. 0's or

2. 111* 's or

3. Repeatedly produce both 0's and 111* 's or 111* 's and 0's.

11+ : It produce string ateleast one one followed by one or more number of 1's.

1c)

L is the language of odd decimal integers greater than 0.

[1-9] : It matches any character between 1 to 9.

[0-9]* : matches zero or more digits

(1|3|5|7|9) : Repeat the numbers production

1|3|5|7|9 : Not repeat the numbers production any of the number produced

[1-9][0-9]* (1|3|5|7|9) | 1|3|5|7|9

Therefore it produce the language of odd decimal integers greater than 0.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.