L = { 0nw1n/ n >= 0, w {0,1}* }
[10 marks] We know from our discussion that the language Onlnln-0} is not regular. Is the language L {0"w1nIn 〉 0,...
3. [5 marks] Is the language L = {o € {a, b}* | |0la- l0b is divisible by 2",n 2 1} regular? Be sure to prove your answer 3. [5 marks] Is the language L = {o € {a, b}* | |0la- l0b is divisible by 2",n 2 1} regular? Be sure to prove your answer
(d) Let L be any regular language. Use the Pumping Lemma to show that In > 1 such that for all w E L such that|> n, there is another string ve L such that lvl <n. (4 marks) (e) Let L be a regular language over {0,1}. Show how we can use the previous result to show that in order to determine whether or not L is empty, we need only test at most 2" – 1 strings. (2...
6.[15 points] Recall the pumping lemma for regular languages: Theorem: For every regular language L, there exists a pumping length p such that, if s€Lwith s 2 p, then we can write s xyz with (i) xy'z E L for each i 2 0, (ii) ly > 0, and (iii) kyl Sp. Prove that A ={a3"b"c?" | n 2 0 } is not a regular language. S= 6.[15 points] Recall the pumping lemma for regular languages: Theorem: For every regular...
Suppose that L is a regular language. Prove that the language p r e f i x (L )={w | x, wx L } is regular. (For example, if L = {abc, def}, prefix(L) = {?, a, ab, abc, d, de, def}.)
2. If L is a regular language, prove that the language 11 = { uv/ u E 1 , |v|-2) is also regular. (Hint: Can you build an NFA of L1 using an NFA of a language L? Use N, the NFA of the language L)
Prove that the following language is not regular: L = { w | w ∈ {a,b,c,d,e}* and w = wr}. So L is a palindrome made up of the letters a, b, c, d, and e.
Consider the language L below. (a) Is L a regular language? – Yes, or No. (b) If L is a regular language, design the DFA (using a State Table) to accept the language L, with the minimum number of states. Assume , (c) Suppose the input is “101100”. Is this input string in the language L? Σ = {0,1} L={w l w has both an even number of O's and an odd number of 1's}
Prove that the language L = {0^n1^m0^n | m, n greaterthanorequalto 0} is not regular.
Write a legal regular expression for the following regular language. L = { w | w ∊ (0 + 1)* and w contains an even number of 1’s AND an even number of 0’s}.
determine if the language is regular, context-free, Turing-decidable, or undecidable. For languages that are regular, give a DFA that accepts the language, a regular expression that generates the language, and a maximal list of strings that are pairwise distinguishable with respect to the language. For languages that are context-free but not regular, prove that the language is not regular and either give a context- free grammar that generates the language or a pushdown automaton that accepts the language. You need...