I need help with question 2 please. Example ProofProve that the language B = {0"1"|n > 0} is not a regular language.Proof. Assume that B is regular and let p be the pumping length for thelanguage. Choose the string s = 0P1P so that |s| > p. By the pumpinglemma (PL) for regular languages, we can partition s = xyz so that for anyi > 0, s' = xy' z E B. Let's consider three cases for the partition y:ry'z1. The string (partition) y consists only of 0's. Then, s' = xyyz =has more 0's than l's. Clearly s' 4 B and so condition number 1 ofthe PL is violated. This is a contradiction for our assumption that Bis regular.2. The string (partition) y consists only of l's. Using the same argumentfrom the previous case, we obtain another contradiction.3. The string (partition) y consists of 0's and l's. Then, s' = xyyz = xy²zmay have the same number of 0's and l's, but some of the l's willcome before some of the 0's and violate membership in the languageB. Hence, we have another contradiction with our assumption of reg-ularity.Therefore, we cannot avoid a contradiction with any possible y partition andconclude that the language B cannot be a regular language.InstructionsUse the Pumping Lemma for CFLS to prove that each of the following lan-guages is not context-free.1A = {0"#0²"#0³n | n > 0}. Hint: consider s = 0P#0²r#0³P.C = {w| the number of 1s equals the number of 2s and the number of 3s equals the number of 4sand E = {1,2, 3,4}. Hint: consider s = 1P3P2P4P.

Proof:1. Assume that C = {w | 1's equal to number of 2's, 3's, 4's}2. Assume that w is a word in C3.…

Answered: I need help with question 2 please.

Engineering

Computer Science

I need help with question 2 please.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Consider the language L = {a'bck | i + j,j # k, i + k}; it is not a context- free language. Show that it nevertheless satisfies the conditions of the context-free pumping lemma, that i s, show that there exists an m so that for all strings w in L of length at least m, we can write w = uvxyz with |vxy| 1, such that Vi > 0 : uv'xy'z € L.
Can you please help me with this problem because I don't understand how to do this problem. Can you please help me with this problem. Can you please explain this step by step.
Consider the language L of strings over the alphabet Σ = {a, b} which contain an equal number of a’s and b’s, and the set of b’s is consecutive in the string, e.g., ab, abba, aabb, abbbaa, aaabbbbbaa, etc. Note that ε ∈ L for completeness (0 number of a’s is equal to 0 number of b’s, which are also consecutive). Show that this language is context-free by giving a context-free grammar.
Consider the language L of strings over the alphabet Σ = {a, b} which contain an equal number of a’s and b’s, and the set of b’s is consecutive in the string, e.g., ab, abba, aabb, abbbaa, aaabbbbbaa, etc. Note that ε ∈ L for completeness (0 number of a’s is equal to 0 number of b’s, which are also consecutive). Show that this language is context-free by giving a context-free grammar. Please make sure to test the answers onhttps://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/
Consider the language L of strings over the alphabet Σ = {a, b} which contain an equal number of a’s and b’s, and the set of b’s is consecutive in the string, e.g., ab, abba, aabb, abbbaa, aaabbbbbaa, etc. Note that ε ∈ L for completeness (0 number of a’s is equal to 0 number of b’s, which are also consecutive). Show that this language is context-free by giving a context-free grammar. I want a CFG
Consider the language L = {a i b j c k | i 6= j, j 6= k, i 6= k}; it is not a context- free language. Show that it nevertheless satisfies the conditions of the context-free pumping lemma, that i s, show that there exists an m so that for all strings w in L of length at least m, we can write w = uvxyz with |vxy| ≤ m, |vy| ≥ 1, such that ∀i ≥ 0 : uvixyi z ∈ L.
Let Σ be the alphabet {a,b}. Let L be the language describe by Σ∗ − (ε|Σ∗b)aa(ε|bΣ∗), where the hyphen denotes set difference and ε de- notes the empty string. (Hint: L consists of the strings over Σ in which no maximal substring consisting solely of a’s is of length 2.) Draw a finite automa- ton that accepts L.
A palindrome is a string that reads the same backward as forward, i.e., w = wR. A palindromic language is one in which all the strings are palindromes, i.e., some subset of P = {w | w ∈ Σ∗ and w = wR} Consider the language L ={<B> | B is a DFA with input alphabet Σ and L(B) contains a palindrome}. Show that L is decidable. Explain step by step.
Prove that the following languages are not regular using the Pumping lemma and/or closure properties. Note: Do not use other methods. a. L1 = {w ∈ {a, b}∗: na(w) + nb(w) = 3 · nb(w)} (na (w) is used to denote the number of a's in the string w) b. L2 = {anbmck: n, m, k ∈ ℕ, n < m or n < k}
Use a closure operation to reduce the language L of all even-lengthed strings of as and bs where both halves of the string end with an a, that is L = {w0aw1a | w0,w1 ∈ {a,b}∗ ∧ |w0| = |w1|}, to a simpler language L0 which must also be regular if L is regular. Use the pumping lemma to show L0 is not regular.
Let Z = { 0 0 ! , 0 1 ! , 1 0 ! , 1 1 ! }. Decide whether each of the following languages over Σ is regular: • The set of all strings such that the “top row” is the reverse of the bottom “row.” For instance, 0 0 ! 1 0 ! 0 1 ! 0 0 ! ∈ L, and 0 0 ! 1 1 ! 0 1 ! 0 0 ! ∈/ L, • The set of all strings such that the “top row” is the complement of the bottom “row.”
Let L be a language over the alphabet Σ = {a, b, c}. Prove that L = {aªbman for any positive integers n ‡m} is not regular. Proof: Assume that L is regular, so that the pumping lemma applies. Therefore L has a pumping length p. Let Since s belongs to L and S = This string is a member of L because has length longer than p, there exist strings x, y, and z such that s = xyz, where xz is a member of L, xyz is a member of L for all positive integers i, − [y] >0, and − |xy| ≤ p. Now consider the following argument: (You finish the rest of the proof.)