3. These languages are not regular. For each, list three strings that would work in a...
3. These languages are not regular. For each, list three strings that would work in a Pumping
Lemma proof. Then, use one of them to show the language is not regular. But not a.
a. L = {ww | w Î {a, b}*}
b. L = {anba2n | n >= 0}
c. {w Î S* | w contains more a’s than b’s}.
Homework Answers
a)L = {ww | w Î {a, b}*
Assume L is regular. From the pumping lemma there exists an n such that every w Î L such that |w| >=n can be represented as x y z with |y| not =0 and |xy| <= n. Let us choose an bn an bn . Its length is 4n >= n. Since the length of xy cannot exceed n, y must be of the form a for some k > 0. From the pumping lemma an+1bnanbnmust also be in L but it is not of the right form since the middle of the string would be in the middle of the b which prevents a match with the beginning of the string. Hence the language is not regular.
Add Answer to:
3. These
languages are not regular. For each, list three strings
that would work in a...
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...
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...
6.[15 points] Recall the pumping lemma for regular languages: Theorem: For every regular language L, there...
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...
Prove that the following are not regular languages. Just B and F please Prove that the...
Prove that the following are not regular languages. Just B and F
please
Prove that the following are not regular languages. {0^n1^n | n Greaterthanorequalto 1}. This language, consisting of a string of 0's followed by an equal-length string of l's, is the language L_01 we considered informally at the beginning of the section. Here, you should apply the pumping lemma in the proof. The set of strings of balanced parentheses. These are the strings of characters "(" and ")"...
Exercise 4.1.1: Prove that the following are not regular languages a) (0"1n|n 2 1). This language,...
Exercise 4.1.1: Prove that the following are not regular languages a) (0"1n|n 2 1). This language, consisting of a string of 0's followed by an cqual-length string of 1's, is the language Loi we considered informally at the beginning of the scction. Here, you should apply the pumping lemma in the proof. b) The set of strings of balanced parentheses. These are the strings of char- acters "(" and " that can appear in a well-formed arithmetic expression *c) O"IO"...
(9 pts 3 pts each) For each of the following languages, name the least powerful type of machine that will accept it, an...
(9 pts 3 pts each) For each of the following languages, name the least powerful type of machine that will accept it, and prove your answer. (Hint: a finite state automata is less powerful than a pushdown automata, which in turn is less powerful than a Turing Machine.) For example, to prove a language needs a PDA to accept it, you would use the Pumping Lemma to show it is not regular, and then build the PDA or CFG that...
(9 pts 3 pts each) For each of the following languages, name the least powerful type of machine that will accept it...
(9 pts 3 pts each) For each of the following languages, name the least powerful type of machine that will accept it, and prove your answer. (Hint: a finite state automata is less powerful than a pushdown automata, which in turn is less powerful than a Turing Machine.) For example, to prove a language needs a PDA to accept it, you would use the Pumping Lemma to show it is not regular, and then build the PDA or CFG that...
For each of the following problems, decide whether the set A is regular. If the set is regular, g...
For each of the following problems, decide whether the set A is
regular. If the set is regular, give a FSM that recognizes it; if
the set is not regular, prove it using the pumping lemma. 1.
A={s11s | s∈{0}∗} Thus the strings 00011000 and 000001100000 are
elements of A, but 00100 and 001100000 are not. 2. A={r11s |
r,s∈{0}∗} Thus the strings 001100 and 0110000 are elements of A,
but 00111100 and 000010 are not. 3. A={w∈{a,b}∗ | w...
Prove if the following languages are CFL or not. If L is a CFL, give...
Prove if the following languages are CFL or not.
If L is a CFL, give its
CFG. Otherwise, prove it by Pumping Lemma.
If any closure property of
CFL is applicable, apply them to simplify it before its proof.
L = {wwRw | w {a,
b}*}
L =
{anbjanbj|
n >= 0, j >= 0}
L =
{anbjajbn|
n >= 0, j >= 0}
1. Give a context-free grammar for the set BAL of balanced strings of delimiters of three...
1. Give a context-free grammar for the set BAL of balanced strings of delimiters of three types (), and . For example, (OOis in BAL but [) is not. Give a nondeterministic pushdown automata that recognizes the set of strings in BAL as defined in problem 1 above. Acceptance should be by accept state. 2. Give a context free grammar for the language L where L-(a"b'am I n>-o and there exists k>-o such that m-2*ktn) 3. Give a nondeterministic pushdown...
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...
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...
Prove that the following are not regular languages. Just B and F
please
Prove that the following are not regular languages. {0^n1^n | n Greaterthanorequalto 1}. This language, consisting of a string of 0's followed by an equal-length string of l's, is the language L_01 we considered informally at the beginning of the section. Here, you should apply the pumping lemma in the proof. The set of strings of balanced parentheses. These are the strings of characters "(" and ")"...
Exercise 4.1.1: Prove that the following are not regular languages a) (0"1n|n 2 1). This language, consisting of a string of 0's followed by an cqual-length string of 1's, is the language Loi we considered informally at the beginning of the scction. Here, you should apply the pumping lemma in the proof. b) The set of strings of balanced parentheses. These are the strings of char- acters "(" and " that can appear in a well-formed arithmetic expression *c) O"IO"...
(9 pts 3 pts each) For each of the following languages, name the least powerful type of machine that will accept it, and prove your answer. (Hint: a finite state automata is less powerful than a pushdown automata, which in turn is less powerful than a Turing Machine.) For example, to prove a language needs a PDA to accept it, you would use the Pumping Lemma to show it is not regular, and then build the PDA or CFG that...
(9 pts 3 pts each) For each of the following languages, name the least powerful type of machine that will accept it, and prove your answer. (Hint: a finite state automata is less powerful than a pushdown automata, which in turn is less powerful than a Turing Machine.) For example, to prove a language needs a PDA to accept it, you would use the Pumping Lemma to show it is not regular, and then build the PDA or CFG that...
For each of the following problems, decide whether the set A is
regular. If the set is regular, give a FSM that recognizes it; if
the set is not regular, prove it using the pumping lemma. 1.
A={s11s | s∈{0}∗} Thus the strings 00011000 and 000001100000 are
elements of A, but 00100 and 001100000 are not. 2. A={r11s |
r,s∈{0}∗} Thus the strings 001100 and 0110000 are elements of A,
but 00111100 and 000010 are not. 3. A={w∈{a,b}∗ | w...
Prove if the following languages are CFL or not.
If L is a CFL, give its
CFG. Otherwise, prove it by Pumping Lemma.
If any closure property of
CFL is applicable, apply them to simplify it before its proof.
L = {wwRw | w {a,
b}*}
L =
{anbjanbj|
n >= 0, j >= 0}
L =
{anbjajbn|
n >= 0, j >= 0}
1. Give a context-free grammar for the set BAL of balanced strings of delimiters of three types (), and . For example, (OOis in BAL but [) is not. Give a nondeterministic pushdown automata that recognizes the set of strings in BAL as defined in problem 1 above. Acceptance should be by accept state. 2. Give a context free grammar for the language L where L-(a"b'am I n>-o and there exists k>-o such that m-2*ktn) 3. Give a nondeterministic pushdown...
Most questions answered within 3 hours.
-
You have just been hired by FAB Corporation, the manufacturer of
a revolutionary new garage door...
asked 4 minutes ago -
5) Determine Ka for Phosphoric acid. In a 1.0 M
solution of this acid when the...
asked 8 minutes ago -
Data is taken on 773 randomly selected adults who are at least
20 years old. The...
asked 18 minutes ago -
Discuss the importance of laws such as the Americans with
Disabilities Act and the Civil Rights...
asked 16 minutes ago -
1. Expected cash dividends are $2.50, the dividend yield is 7%,
flotation costs are 5%, and...
asked 23 minutes ago -
Your code should contain appropriate validations and must focus
on code optimization. Briefly, explain (150-200 words)...
asked 21 minutes ago -
Schuepfer Inc. bases its selling and administrative expense
budget on budgeted unit sales. The sales budget...
asked 22 minutes ago -
A nutritionist claimed that the mean daily calcium intake for
California women was 1000 milligrams. A...
asked 37 minutes ago -
Arbitron Media Research Inc. conducted a study of the iPod
listening habits of men and women....
asked 44 minutes ago -
Code in JAVA....................
Guess the Number
In this activity, you will write a REST server to...
asked 37 minutes ago -
2. A 2 kilo-ohm resistor is connected in series to an inductor
and a 2000 V...
asked 44 minutes ago -
A damped LC circuit loses 6.0% of its electromagnetic energy per
cycle to thermal energy.
Part...
asked 51 minutes ago