Using Pumping Lemma (slides 30-35 of the notes 'Regular Languages & Finite Automata-IV') one can show the language L= {a"b" |n € N} is not regular (We need this property in the notes 'Context-free Languages and Pushdown Automata I). This is done by way of contradiction. We assume L is regular. Since L is infinite, Pumping Lemma applies. We then consider the string s = ambm where m is the number of states in the DFA that recognizes L. Since the length of s is bigger than m, by Pumping Lemma, there exists strings x,y and z such that s = xyz, y# A, |xy|< 2m and xykz EL for all k e N. If |xy| < 2m then the first repeated state on the acceptance path cannot be a final state. Is this statement true, why or why not?

Using Pumping Lemma (slides 30-35 of the notes 'Regular Languages & Finite Automata-IV') one can show the language L= {a"b" |n € N} is not regular (We need this property in the notes 'Context-free Languages and Pushdown Automata I). This is done by way of contradiction. We assume L is regular. Since L is infinite, Pumping Lemma applies. We then consider the string s = ambm where m is the number of states in the DFA that recognizes L. Since the length of s is bigger than m, by Pumping Lemma, there exists strings x,y and z such that s = xyz, y# A, |xy|< 2m and xykz EL for all k e N. If |xy| < 2m then the first repeated state on the acceptance path cannot be a final state. Is this statement true, why or why not?

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

Related questions

Q: need to create a basic Non-Determinitsic Finite Automata NFA starts with a symbol and ends with…

A: The regular expression for the language accepted by NFA is 1(0+1)*0 + 0(0+1)*1

Q: How would I draw a DFA (Deterministic Finite Automaton) for the following language? - {} (A…

A: Answer to the above question is in step2.

Q: Consider the following languages over Σ = {0,1} for L2 is the language of all strings that do not…

A: Defined over the alphabet Σ = {0,1}, language L2 is made up of strings devoid of the pattern "00".…

Q: 10. a. Define clearly but completely: Language L is decidable. b. Let ALLDFA = {M: M is a DFA and…

A: A language L is decidable or recognisable if a Turing machine that recognises (decides) that…

Q: Give a regular expression for the smallest language Lover Σ = {a,b,c} such that EEL • aa EL Vr E L,…

A: A regular expression is a character sequence that describes a text search pattern. String-searching…

Q: Consider the decidable language ALLNFA= {IN is a NFA and N accepts all strings over }. Construct the…

A: Decidable Some Turing machines never go into an infinite loop, they are always in halt. Turing…

Q: Given the language L(r) defined over the alphabet {a,b} where r = b(aabb)*a: a. Define a PDA that…

A: We are given a language L(r) , where r = b(aabb)*a and we are going to design PDA for it. Then we…

Q: Exercise 4 (Ex. 10, Chapter 2 of [Martin; 2011]). Let Mi and M: be the finite automata pictured…

A: Finite Automata: It can be classified into two types Deterministic Finite Automaton (DFA)…

Q: For the set s={a,b} a) Draw the Deterministic finite automata (DFA) which accepts all stings having…

A: First of all let's understand what is DFA? In DFA from every state for every symbol only one…

Q: a) Prove that the following language is NOT a CFL using the CFL pumping lemma. L = { 0m1=0m |n >m}…

A: Solution:

Q: Let L be the set of exactly those strings over the alphabet {a, b, c, g} whose last symbol is either…

A: Transition function : that takes as arguments a state and an input symbol and returns a state.…

Q: Prove that the following language is non-regular, using the Pumping Lemma. L = {ambcr | m, n, r =…

A: The pumping lemma is a fundamental result in formal language theory that provides a way to prove…

Q: Find CFGs that for these regular languages over the alphabet Σ = {a, b}. Draw a Finite Automatafirst…

A: Let's tackle each of these languages one by one.(a) Language of all words containing the substring…

Q: 1. Give a state diagram for a deterministic finite automaton that recognizes the following language…

A: Below i have drawn the DFA

Q: Exercise4: Consider the language L on = {0,1} with L= {w such that w starts with 1and ends with 00}…

Q: Draw the state diagram of a FINITE AUTOMATON (not DFA) that accepts the language of all strings over…

Q: Assume that we want to use the Pumping Lemma to prove the language L is not a regular language. Here…

A: The objective of the question is to use the Pumping Lemma to prove that a given language L is not a…

Concept explainers

Bare bones programming language

Bare bones programming language is a low-level programming language that gives a detailed stepwise description of a program. It has a tight program design and in-depth understanding of the toolchain. It is based on the target environment and is used for safe coding practices. C programming language is a type of bare bones programming language.

Question

100%

2. Using Pumping Lemma (slides 30-35 of the notes 'Regular Languages & Finite
Automata-IV') one can show the language L= {a"b" | n€N } is not regular (We need
this property in the notes 'Context-free Languages and Pushdown Automata I). This is
done by way of contradiction. We assume L is regular. Since L is infinite, Pumping
Lemma applies. We then consider the string s = ambm where m is the number of
states in the DFA that recognizes L. Since the length of s is bigger than m, by Pumping
Lemma, there exists strings x,y and z such that s = xyz, y + A, |xy| < 2m and
xykz eL for all k e N. If |xy| < 2m then the first repeated state on the acceptance
path cannot be a final state. Is this statement true, why or why not?

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1 Pumping Lemma Theorem

VIEW

Step 2 Explaination

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 2 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

on A language L is called slithy if it contains at least two strings and has the following property: For every two strings x, y in L such that |x|< lyl, the string obtained by taking the first letter of y and inserting it at the start of x is also in L. For example, if L contains aaa and baaba, then it must also contain the string baaa. Prove by contradiction that every slithy language contains two strings of the same length.
We have introduced some languages involving DFA/NFA that are decidable. For example, we have introduced EDFA = {{B)|B is a DFA and L(B) = Ø}, which can be decide by a TM DEDFA . We can construct TM DEDFA in this way: given (B), DEDFA will mark the states of B to check whether finally any accept state can be marked. Furthermore, we have used this TM DEDFA to construct a TM decider for another language EQDFA = {{A,B)| A,B are DFAS and L(A) = L(B)}. See the allowed lecture slides for details. Now, follow this idea, use this DEDFA to construct another Turing machine DSUB that decide the language SUBDFA = {(A,B>| A,B are DFAS, L(A) C L(B)}.
on A language L is called slithy if it contains at least two strings and has the following property: For every two strings x, y in L such that |x|< lyl, the string obtained by taking the first letter of y and inserting it at the start of x is also in L. For example, if L contains aaa and baaba, then it must also contain the string baaa. Prove by contradiction that every slithy language contains two strings of the same length.
Why It is not possible to design a general finite automata for checking a string in the form ?
Draw a nondeterministic finite automaton (NFA) that recognizes the language of strings of lowercasealphabetic characters which don't violate the rule "'i' before 'e' except (directly) after 'c'." Thealphabet should be just the letters 'c', 'e', 'i', and 'x', where 'x' will stand for all lowercase letters otherthat 'c', 'e', and 'i.' Use JFLAP and submit the saved file.
on A language L is called slithy if it contains at least two strings and has the following property: For every two strings x, y in L such that |x|< lyl, the string obtained by taking the first letter of y and inserting it at the start of x is also in L. For example, if L contains aaa and baaba, then it must also contain the string baaa. Prove by contradiction that every slithy language contains two strings of the same length.
Consider the Finite Automata D in Figure 2. a. List 3 strings of different lengths that D accepts and also 3 that it rejects. b. What is the shortest string that D accepts? What is the shortest string that D rejects? c. Describe, in your own words, what is the language of D, i.e., L(D). 93 42 Figure 2. Finite automata D
In a proof that L= {a"ba" | n2 0} is not a regular language you would assume a L is regular with pumping length p and then pick a string that would allow an easy contradiction using the pumping lemma. Give an example suitable string for this purpose, and explain very briefly why it is a good choice.
Question 5 Let I be the set of all even length binary strings. (So I is decidable.) Give an example of a language K ⊆ I with K undecidable. Here you need to define the set K and state your reasoning why the K you define is undecidable. Full explain this question very fast solution sent me step by step text typ work only