## validation of a pumping lemma proof for regular languages

i have the following regular expression:

of course i could think of a world like w=a^(m+2)b^(m+2)c^(2m+3) and continue with the proof BUT i was just wondering, because L is made up of a union of two expressions, is it valid to split L into L1=a^(i)b^(j)c^(2j-1)| i<=j & i,j>0 L2=a^(i)b^(j)c^(2j-1)| i>=2j-1 & i,j>0

show for each L1 and L2 that the pummping lemma does not work on them (so for l1 i just show that for lets say each k i is not smaller or equal to j, and for l2 i show that i is not always bigger or equal to 2j-1 for each k)

by that i show that l1 and l2 are not regular which means that the union of the two will also be not regular.. is this corrent?

thank you.

## Proof that a language is not regular using the pumping lemma

I do not understand the last sentence of the proof provided. It says that the fact that xz does not belong to L contradicts the hypothesis, but isn’t it that xyz not belonging to L what we are trying to prove?

## Pumping lemma for regular languages vs. Pumping lemma for context-free languages

How can I prove the next claim:

If a language $$L$$ meets the pumping lemma for regular languages then $$L$$ meets the pumping lemma for context-free languages?

(Without any pre-condition about the regularity of $$L$$)

## L = {x / |x| = 3}. Is this language regular?

L = { x / |x| = 3 }

Assume that x belongs to alphabet {0,1}. I think the above language is regular. A DFA can be used to determine the above language. Am i correct? Is the above language regular?

If this language L is regular, then it should satisfy pumping lemma. Then there exist w = xyz, where y can be raised to any power of n >= 0. And still the resulting string would be in the language L.

But on the other hand, if we pump more letters then the resulting string will not be in the language. The language L only accepts string of length 3.

Pumping Lemma states that for every regular language there exists an integer p, such that string w of at-least length p can be written as w = xyz and y can be pumped.

Here are my doubts.

1. Is this language L regular?
2. If so does it satisfy Pumping Lemma?
3. Pumping Lemma states that every regular language has a pumping length p >=1. Does this language does not have one?

## What is the computational complexity of “real-life” regular expressions?

Regular expressions in the sense as equivalent to regular (Chomsky type 3) languages know concatenation xy, alternation (x|y), and the Kleenee star x*.

"Real-life" regular expressions as used in programming usually have a lot more operations available; amongst others, quantification x{n}, negation [^x], positive and negative lookahead x(?=y), or back-reference \n.

There is a famous post on SO stating that regular expressions can not be used to parse HTML for the reason that HTML is not a regular language.

My question is: Is this accurate? Do "real-life" regular expressions, say the selection defined in the Java docs, really have the same expressive power as regular expressions as understood in formal language theory; or do the additional constructs, although possibly not strong enough to capture HTML and the like, put common regular expressions further up on the Chomsky scale than just Type 3 languages?

I would imagine the proof of the computational equality of the two would amount to showing that each operation available for the common regexp is just syntactic sugar and can be expressed by means of the 3 basic operations (concatenation, alternation, Kleene start) alone; but I am finding it hard to see how one would e.g. simulate back-reference with classic regexes alone.

## Is this language L = {w $\in$ {a,b}$^*$ : ($\exists n \in \mathbb{N}$)[$w|_b = 5^n$]} regular?

Let’s say we have the language L = {w $$\in$$ {a,b}$$^*$$ : ($$\exists n \in \mathbb{N}$$)[$$w|_b = 5^n$$]}. I want to know if this is a regular language or not. How do I go about doing this? I’m familiar with the Myhill-Nerode theorem but I don’t know how to apply it.

## My group is obsessed with everyone attending the Session, which destroy’s any regular playing [closed]

I don’t know if this is a weird thing to ask.

However, my group consists of 5 Players and our DM. They’re great people and every Session is a lot of fun, ngl. The issue I’m having is that -for whatever reason- everyone (except me apparently) refuses to even think about playing if one of the Players isn’t attending.
Scheduling is difficult even when accepting losses. But only playing when everyone can attend, makes it impossible and I really don’t want a Campaign that runs once a month, if we’re lucky. Maybe I am just in my bubble since I have rather flexible working times.
But I just cannot understand, why one, or even two players being absent, would be a huge problem. I’ve been DMming myself for a while, rebalancing is annoying, but not impossible, even on the fly. A PC could be played by the DM or the PC does something in their Downtime while the group does something else, which explains why they aren’t there. For a big and important story arch, I would understand that everyone should ideally be there but even then one player not being there wouldn’t kill anyone. Especially since the Campaign is made in mind that players and PC’s are interchangeable and until now we haven’t gotten to a point where it was fundamentally important that everyone was there… If three players (more than 50%) can’t make it, then yeah, I understand cancelling a Session. But certainly not at 1-2 Players out of 5.

I just kinda want to hear your opinion. Either I am dumb for thinking that way, or I am not the only one here thinking that way

## When proving a set is not regular is it enough to prove a subset of it regular?

E.g. when proving L = {w in {a,b}^*: the first, the middle, and the last characters of w are identical}, can i just prove ab^pab^pa is not regular? Where p is the pumping length?

## Oracle PL-SQL “Regular expression” to replace each “(space)and(space)” with ‘,’ in a string

I have a string like this x=y and g=h and u=1 and I need to replace each (space)and(space) with ,. I’m using the powerful regular_expression for this but it does not give me the desired result.

select regexp_replace('x=y and g=h and u=1','(^[[:space:]]*)AND(^[[:space:]]*)', ',') from dual; 

I was wondering if you could help me out here. thanks in advance.

## Regular languages, automata

I want to ask about the definition of regular languages. My book says there has to exist a deterministic finite automaton that recognizes it. Does this mean the finite automaton recognizes exactly this language and nothing else or it can recognize possibly some other words not in the language?