For each of the following languages prove that they are regular by giving a fini
ID: 3599739 • Letter: F
Question
For each of the following languages prove that they are regular by giving a finite automaton or regular expression for the language or show they are not regular by providing a pumping lemma or closure property proof for the language.
L! = { w {0,1 } *lw encodes a binary number with no leading zeros that is a power of two! 2 { w E {0, 1)" lw has an equal number of occurrences of the substrings 01 and 10} 3 = {w {0,1} * lw has an equal number of occurrences of the substrings 00 and 111 L5-Onl n is a prime integer)Explanation / Answer
Answer:
l. Ll=[wc[0,l]* | w encodes a binary number with no leading zeros that is a power of two]
L1 is regular.
Proof:
The regular expression for generating L1 is
Regular expression = 10*
2. L2=[we[0,l]*| w has an equal number of occurrences of the substrings 01 and 10]
L2 is regular.
Proof:
The below regular expression produces the strings for L2,
Regular expression = 0 U 1 U s U 1(0U 1)*1U 0(0 U 1)‘0
3. L3=[wc [0,l]* | w has an equal number of occurrences of the substrings 00 and ll]
L3 is regular.
Proof:
The below regular expression makes the strings for the L3,
Regular expression = (10 + 0)*(1 + 10)*
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.