Hello, I need help solving this computer science problem. 1) Use the Pumping Lemma to show...

Question

Question

Hello, I need help solving this computer science problem.

1) Use the Pumping Lemma to show that the set of all binary strings of length a power of 2 is not regular.

Answer 1

Answer #1

answer)

length power of 2 means length is 0,2,4,8,16,......

pumping lemma for regular languages:

1)assume given language is regular and there exist a finite automata with 2k states.

2)take a valid string z from L.

z=1010

3)divide the string z into 3 parts,U,V,W in such a way that |V|>=1 and |UV|<=2k

U=10

V=1

W=0

4)if for any value of i, UV^IW belongs to L then L is regular otherwise L is not regular.

say i=2 then UVⁱW becomes 10110 (here length is not power of 2)this is not belongs to L

this is contradiction to given statement.

therefore L is not regular.

Answer 2

Similar Homework Help Questions

Hello, I need help solving these two computer science questions. 3. Give a CFG for each...

Hello, I need help solving these two computer science questions. 3. Give a CFG for each of the following: (a) The language {0416 with a +b}. (b) All binary palindromes with exactly three 1's (such as 001010100). 4. Consider the following CFG with start state S: SOAS 1BS € A → OAA 1 B + 1BBO Determine the language generated by S. Justify your answer.
Pumping lemma s. (7+5 points) Pumping lemma for regular languages. In all cases, -a,b) a) Consider...

Pumping lemma s. (7+5 points) Pumping lemma for regular languages. In all cases, -a,b) a) Consider the following regular language A. ping length p 2 1. For each string s e pumping lemma, we can write s -xy, with lyl S p, and s can be pumped. Since A is regular, A satisfies the pumping lemma with pum A, where Is] 2 p, by the a) Is p 3 a pumping length for language 4? (Yes/No) b) Show that w...
Use the pumping lemma to show that the following language is non-regular: [a"b2n,n> 1) 1) usually...

Use the pumping lemma to show that the following language is non-regular: [a"b2n,n> 1) 1) usually we need to find a word in the language as an example, what length of the word we should use as the example? what are the three possible ways to choose substring y in the pumping lemma? if a language satisfy the pumping lemma, is this language a regular language? Why?

Use pumping lemma to show that whether L ={ aib3i | i≥1000 and i≤4000} is non-regular...

Use pumping lemma to show that whether L ={ aib3i | i≥1000 and i≤4000} is non-regular or regular. Show your steps against each of the pumping lemma claims.
Can someone use pumping Lemma to show if these are regular languages or not c) Is...

Can someone use pumping Lemma to show if these are regular languages or not c) Is L regular? give a finite automaton or prove using pumping lemma. (d) Is L context-free? give a context-free grammar or pushdown automaton, otherwise pr using pumping lemma. (16 pts)Given the set PRIMES (aP | p is prime (a) Prove that PRIMES is not regular. (b) Prove that PRIMES is not context-free. (c) Show if complement of PRIMES (PRIMES ) is regular or not. d)...
Show that there exists a non-regular language that satisfies the pumping lemma. In particular, yo...

Show that there exists a non-regular language that satisfies the pumping lemma. In particular, you can consider the following language. nan . You need to show that (1) L is not regular, and (2) L satisfies the pumping lemma. Show that there exists a non-regular language that satisfies the pumping lemma. In particular, you can consider the following language. nan . You need to show that (1) L is not regular, and (2) L satisfies the pumping lemma.

(d) Let L be any regular language. Use the Pumping Lemma to show that In >...

(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...
Use the pumping lemma to show that the following language is not regular: L = {bi...

Use the pumping lemma to show that the following language is not regular: L = {bi ajbi : i, j ≥ 1}
Use the CFL (Context Free Language) Pumping Lemma to show each of the following language not...

Use the CFL (Context Free Language) Pumping Lemma to show each of the following language not to be context-free: a) {a^n b^n c^i | i < n} b) {www | w is a binary string over {0,1}} SHOW ALL WORK AND LEAVE NO STEPS OUT!! NEED THIS ASAP! THANKS!!

3. Use the pumping lemma to prove the following language is not regular . Use the...

3. Use the pumping lemma to prove the following language is not regular . Use the pumping lemma to prove the following language is not regular Where is the stringwbut with all the Os replaced by Is and all the し1 = {te E Σ.ead I te _ wu) is replaced by 0s. For example, if w = 00110 then w = 11001.