Use the pumping lemma to show that the following languages are not regular languages L = {an bm | n = 2m}
Use the pumping lemma to show that the following languages are not regular languages L = {anbm | n = 2m}
596 Views Asked by alaa raed At
2
There are 2 best solutions below
1
Netaji
On
L={anbm|n=2m} Assume that L is regular Language Let the pumping length be p L={a2mbm} Since |s|=3m > m (total string length) take a string s S= aaaaa...aabbb....bbb (a2mbm times taken) Then, u = am-1 ; v= a ; w= ambm. && |uv|<=m Now If i=2 then S= am-1 a2 ambm = a2m-1bm Since here we are getting an extra a in the string S which is no belong to the given language a2mbm our assumption is wrong Therefore it is not a regular Language
Related Questions in REGULAR-LANGUAGE
- Correct labeling for this regular language?
- How to use JavaScript's sql-formatter library to parse a SQL statement that contains the nested concat function in the where condition
- What regular expression will match a string of letter "U"s and letter "O"s where at most one pair of (U, O) or (O, U) appear next to each-other?
- How can I generate a Context Free Grammar for a specific language
- how to prove {(a^m)(b^n)(c^k): m!=k and m,n,k ∈ N} is non-regular?
- Jenkins - To trigger pipeline only for event failed or successful for jenkins webhook trigger
- How to write a generical REGEX expression to: Σ = {a, b, c}, L = {w ∈ Σ ∗ / the first symbol of w is equal to the last symbol of w}?
- How can I allow a single space in a regex in Dart but allow other characters to be 1 or more?
- How remove numbers from url using RewriteRule in .htaccess file?
- Regular expressions matching given string
- How do the kleene plus operators apply here?
- Automata theory: Formal definition of indistinguishable & distinguishable strings and example confusion
- Accept an optional substring with Lark's LALR(1) parser
- Match bitwise operators in lex
- concatenation of a context-free language
Related Questions in AUTOMATA
- Converting ENFA To DFA and ENFA NFA
- Need clarification on pumping lemma for context free languages
- Unable to create an DPDA that accepts strings in binary notation multiples of 3
- how to model and verify model
- UPPAAL chooses to loop on instead of a transition of a higher priority
- Build a Turing Machine that counts a's and b's
- Convert the given Moore Machine into Mealy machine
- Converting context free grammar to chomsky normal form
- Intersection of two Deterministic Finite Automata (DFA)
- NFA or e-NFA for the condition , n % 5 = 0 where n is the number of 1s
- Finding a regular grammar for the language L
- Does this DFA satisfy the complement of the given language?
- How to Perform Bottom-Up Parsing for a Given CFG and Input String?
- Regular expressions matching given string
- If an Infinite language is passed to Machine M, the subsidiary which gives a finite solution to the infinite input tape is?
Related Questions in FINITE-AUTOMATA
- a challenging finite automata - what is the language?
- Correct labeling for this regular language?
- Unable to create an DPDA that accepts strings in binary notation multiples of 3
- Need a DFA for the alphabets {a,b} such that the language must contain equal and even numbers of a and b
- Convert the given Moore Machine into Mealy machine
- What is the flaw in the proof of the countability of the set of finite language?
- NFA or e-NFA for the condition , n % 5 = 0 where n is the number of 1s
- Conversion of NFA having a missing transition for any input character on initial state to DFA
- On the use of subsequential symbol $ in Finite state transducers to pad out the context, for composition
- Convert Nondeterministic Finite Automata to Regular Expression
- How do I make a string validator for Deterministic Finite Automata?
- Can Arden's theorem provide multiple regular expressions for a given DFA if the order and process of solving the equations are changed?
- Automata theory: Formal definition of indistinguishable & distinguishable strings and example confusion
- NFA or DFA accepting # of positions of 4k between 0's
- Using bracket for automata
Related Questions in PUMPING-LEMMA
- Why pumping lemma for context free languages do not have bound on first part of string?
- Recognize the type of the given formal language
- concatenation of a context-free language
- Pumping Lemma and Hierachy
- Using string of set length with pumping lemma to prove irregularity
- Can someone help me with this proof about the pumping lemma using coq?
- Why is L = {a^ib^i , 0<i<5} regular?
- Is L = {a^n a^n b^m |m, n ≥ 0} a regular or irregular language?
- Proving if a language is context free with pumping lemma
- Is L = {ww^Ru | w, u ∈ {0,1}+} regular language?
- Regular language demonstration
- How to prove a language with (ab)^n.. is not regular with pumping lemma?
- How to translate this description into a language?
- How to prove that L = {a^j b^k c^k d^k: j, k ≥ 1} ∪ {b^j c^k d^l : j, k, l ≥ 0} satisfies the pumping lemma for CFL’s?
- Operating on a Regular Expression before applying Pumping Lemma
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular # Hahtags
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
Choose a string a^2p b^p. The pumping lemma says we can write this as w = uvx such that |uv| <= p, |v| < 0 and for all natural numbers n, u(v^n)x is also a string in the language. Because |uv| <= p, the substring uv of w consists entirely of instances of the symbol a. Pumping up or down by choosing a value for n other than one guarantees that the number of a's in the resulting string will change, while the number of b's stays the same. Since the number of a's is twice the number of b's only when n = 1, this is a contradiction. Therefore, the language cannot be regular.