Exercise 3: (2marks) Write RE for the language L over 2={0,1} such that all the string...

Question

Question

Answer 1

Answer #1

(&+0+*6+1) > Eto)* + E +1)* o (&+0* produces all strings of any lengths. Since ol shouldnt be present we we should make sure

Answer 2

Similar Homework Help Questions

John Doe claims that the language L, of all strings over the alphabet Σ = {...

John Doe claims that the language L, of all strings over the alphabet Σ = { a, b } that contain an even number of occurrences of the letter ‘a’, is not a regular language. He offers the following “pumping lemma proof”. Explain what is wrong with the “proof” given below. “Pumping Lemma Proof” We assume that L is regular. Then, according to the pumping lemma, every long string in L (of length m or more) must be “pumpable”. We...
1. L is the set of strings over {a, b) that begin with a and do...

1. L is the set of strings over {a, b) that begin with a and do not contain the substring bb. a. Show L is regular by giving a regular expression that denotes the language. b. Show L is regular by giving a DETERMINISTIC finite automaton that recognizes the language.
I need to construct a deterministic finite automata, DFA M, such that language of M, L(M),...

I need to construct a deterministic finite automata, DFA M, such that language of M, L(M), is the set of all strings over the alphabet {a,b} in which every substring of length four has at least one b. Note: every substring with length less than four is in this language. For example, aba is in L(M) because there are no substrings of at least 4 so every substring of at least 4 contains at least one b. abaaab is in...

1(a)Draw the state diagram for a DFA for accepting the following language over alphabet {0,1}: {w...

1(a)Draw the state diagram for a DFA for accepting the following language over alphabet {0,1}: {w | the length of w is at least 2 and has the same symbol in its 2nd and last positions} (b)Draw the state diagram for an NFA for accepting the following language over alphabet {0,1} (Use as few states as possible): {w | w is of the form 1*(01 ∪ 10*)*} (c)If A is a language with alphabet Σ, the complement of A is...
Problem 3.3: For a string x € {0,1}*, let af denote the string obtained by changing...

Problem 3.3: For a string x € {0,1}*, let af denote the string obtained by changing all 0's to l's and all l's to O's in x. Given a language L over the alphabet {0,1}, define FLIP-SUBSTR(L) = {uvFw: Uvw E L, U, V, w € {0, 1}*}. Prove that if L is regular, then FLIP-SUBSTR(L) is regular. (For example, (1011)F = 0100. If 1011011 e L, then 1000111 = 10(110) F11 € FLIP-SUBSTR(L). For another example, FLIP-SUBSTR(0*1*) = 0*1*0*1*.)...
1. Let £ = {0,1} and consider the language L of all binary strings of odd...

1. Let £ = {0,1} and consider the language L of all binary strings of odd length with a 0 in the middle. Give a Turing machine that decide L.

please I need it urgent thanks. subject programming language and compilers w does not contain Question...

please I need it urgent thanks. subject programming language and compilers w does not contain Question 2 Consider the following language over the alphabet = {a,b}: L = {w the substring aa} 1. What is I, the complement of L? 2. Write a regular expression for L. 3. Write a regular expression for L. 4. Design a DFA for I. 5. Modify the DFA for I to make it a DFA for L.
Let L be the language over {a, b, c} accepting all strings so that:

1. Let L be the language over {a, b, c} accepting all strings so that: 1. No b's occur before the first c. 2. No a's occur after the first c. 3. The last symbol of the string is b. 4. Each b that is not the last symbol is immediately followed by at least two d's. Choose any constructive method you wish, and demonstrate that L is regular. You do not need an inductive proof, but you should explain how your construction accounts for...
(1) Write a regular expression for the language. (2) Define a finite state machine (FSM) that...

(1) Write a regular expression for the language. (2) Define a finite state machine (FSM) that recognizes words in the language (input alphabet, states, start state, state transition table, and accept states). Include a state digraph for the FSM. A: For alphabet {p,q,r}, all strings that contain the substring rqr or end with pp.

2. a. Draw a NFA that accepts all strings over Σ = {?, ?} that either...

2. a. Draw a NFA that accepts all strings over Σ = {?, ?} that either end in ?? or contain the substring ??. b. Then convert the NFA in the previous exercise to a DFA