Let E be an alphabet and A C E*. (a) If c E £ and AC E*, we define APPEND.(A) as {wc ɛ E* | w E A}. Prove that, if A is a regular language, then APPEND(A) is a regular language. (b) Let Da be a DFA recognizing A. Describe an NFA NA recognizing APPEND.(A) using only one more state than DA. Give a brief argument that your NFA recognizes A.

Let E be an alphabet and A C E. (a) If c E £ and AC E, we define APPEND.(A) as {wc ɛ E* | w E A}. Prove that, if A is a regular language, then APPEND(A) is a regular language. (b) Let Da be a DFA recognizing A. Describe an NFA NA recognizing APPEND.(A) using only one more state than DA. Give a brief argument that your NFA recognizes A.

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

Giventhegrammar B-> BB | (B) | ε 1.Describe the language it generates 2.Show that it is ambiguous
Can you help me with this probem and the parts that come along with it because i am confused I only need help with part A and part B. Can you please label the problem and can you do it step by step showing work and can you explain it as well. Question that I need help with:1.49 a. Let B = {1 k y| y ∈ {0, 1} ∗ and y contains at least k 1s, for k ≥ 1}. Show that B is a regular language. b. Let C = {1 k y| y ∈ {0, 1} ∗ and y contains at most k 1s, for k ≥ 1}. Show that C isn’t a regular language.
Let A be a language such that A ≤m PCP and ETM ≤m A. What can you say about A? Briefly explain your answer.
2. Let RE be the set of regular expressions over alphabet E = {0, 1}, and for r E RB, let L(r) be the language denoted byr. Consider the claim: VL E P(E"), Vri,ra € RE, (C(r1)) > 1AL\ C(r) = C(ri)) L is regular Either prove this, or find L,ri and ra that provide a counter-example.
Given S = (a, b, c). Prove this language is regular: L = {u ES*:u has at least 1 a, 1 b, and 1 c} using a DFA or NFA or a regular expression for L. Also, explain why your construction is right.
O Given the language L = {(ba)m, amb", aa: m,n 2 0}, find the regular expression r such that L(r) = L.
2. Let RE be the set of regular expressions over alphabet E = {0, 1}, and for r E RE, let L(r) be the language denoted by r. Consider the claim: VL E P(E*),Vr1, r2 E RE, (|L(r1)| > 1 A L \ L(r2) = L(r1)) = L is regular Either prove this, or find L, rı and r2 that provide a counter-example.
Let Σ {a, b, c}. Use the Pumping Lemma to show that the language L defined below is not regular: L = {wb"wR:n > 2, w e {a, c}+}
Use the Pumping Lemma to show the following language L is NOT regular. L= {w E (a, b, c}* ; where w has equal number of a's, b's, and c's}
3. Show that the following language A is not regular using the pumping lemma. A An example of a string in A is 0011111000. = {0n1m+nom | m, n ≥ 0}
Use the pumping lemma to prove that the language L over {a,b,c}*, given by L = {wcv: |wa = |v|b} is not regular.
4. Given a language L, the language L is defined as the language consisting of the reverse of all the strings in L. A language is said to be palindromic, if L = LR. Given a regular language L, how would you check if it is palindromic?