Questions tagged [regular-expressions]

Questions about regular expressions, a formalism to describe regular languages.

Filter by
Sorted by
Tagged with
-3
votes
0answers
17 views

Exercise on star-height [closed]

a) Calculate the star-height of the rational expression $R = ((a^*b)^* ba^*)^*$ . b) What is the star-height of $L( R)$? c) Describe $L(R)$. d) What is the extended star-height of $R$? e) Write a star-...
0
votes
0answers
10 views

I'm having some trouble converting a FA to a RegEx [duplicate]

I was reviewing some of the material that I found about FA to RegEx and while I was practicing with one or another conversion, I came across this FA that I could not pass to RegEx. Would someone be so ...
-2
votes
0answers
15 views

Regular Expression (RE) [duplicate]

Define the Regular Expression of the combination 0 and 1, whereas every 0 always followed by 11 or 111.
1
vote
0answers
17 views

Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular?

Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular? I do not think it is. I recently posted a question and from there I was thinking if this language is regular. If we assume on the contrary, then there ...
1
vote
2answers
24 views

Operations without common elements can not be generated using a finite state automata

I heard that some operations involving regexes that do not have common elements can NOT be generated using a finite automata. I do not remember what it was, where it was from, can anyone tell me what ...
0
votes
1answer
20 views

Is (a+b)* and (ab)* same in finite automata?

Regular language of (a+b)* and (ab)* are: (a+b)* = { ε, a, b, aa , ab , bb , ba, aaa, ...} (ab)* = { ε, a, b, aa, ab, ba, bb, aaa, ... } I am new to Finite automata and this simple notion is ...
0
votes
1answer
26 views

Read regular Expression from NFA

Good evening everyone! Can someone help me with the following task? So we have this NFA: I was supposed to create a regular expression out of it. Now the solution says: $a^{+}b^{+}(c|ca^{*}b^{+})^{*}$...
0
votes
1answer
93 views

What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*)

I have this assignment question to find the pumping length of a regular language (L). The regular expression for the L is given as $(0+0001)((1111)^*+(00)^*)$ What is the length of the longest string ...
0
votes
1answer
24 views

minimum number of states in cross product of two minimum DFAs

If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of ...
-1
votes
1answer
25 views

Proving of regular language [duplicate]

Is this regular or not L = {w1w^R | w ∈ {0,1}* (where for any word w ∈ {0,1})*, w^R denotes the reverse of w)
1
vote
1answer
95 views

What does “lookahead” refer to?

I keep hearing about lookahead parsers, LL parsers, LR, LALR, etc... but no clear explanation behind the etymology of this word. What does "lookahead" refer to? How does this relate to LL, ...
1
vote
2answers
46 views

How to prove that concatenating a language A and A* is commutative?

Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far. If $A$ is ...
1
vote
1answer
36 views

Expert explanation of state elimination methods [duplicate]

I'm so sorry if this question is too general, but I need to understand the general process of the "State elimination method". In other words, what is the general idea, and what is the ...
6
votes
1answer
1k views

Is it possible to build any regular expression in a computer language with just 3 basic operators?

Many computer languages have complex regular expressions tools. For example, in Javascript you have global flags, escape characters, whitespace character, assertions, character classes, groups and ...
0
votes
0answers
24 views

Converting a regular expression to a grammar and regular grammar

I am working on a pretty small lab for my university course and I'm having trouble converting a given regex into a set of regular definitions, then into a grammar and finally a regular grammar. I have ...
0
votes
0answers
22 views

Regular expressions accepted by programming languages but are not regular [duplicate]

The below definition of Regular Language is given in Wikipedia. In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language ...
0
votes
1answer
44 views

a^ib^jc^k, i < j < k is a context-sensitive language, how can prove it as a context sensitive

I've been pondering this question for a long time, that $a^ib^jc^k, i < j < k$ is a context-sensitive language, how we can prove it to be context sensitive or which grammar can generate such a ...
0
votes
1answer
37 views

How to apply Arden's theory to determine a regular expression

If $P=ab$ and $Q=a^*$, how do I use Arden's theorem to determine the regular expression $R$. I'm not sure if I am supposed to just substitute the values of $P$ and $Q$ in the equation $R= Q + RP$. ...
0
votes
2answers
41 views

Can a regular expression be any string from the language described by it? [closed]

Is it possible to have a regular expression from a language (that has strings of infinite length) which it describes ?
0
votes
0answers
29 views

Constant single match regex

I am looking for the name (definition?) of X in: A regular expression is X iff it has exactly one possible match. Examples: <empty regex>, abc, ...
2
votes
1answer
60 views

Extracting regex submatch boundaries without backtracking

I'm attempting to develop from scratch a simple regex engine. I would like for my engine to have the ability to report, "The regex matched on a substring of this line starting at index and ...
1
vote
1answer
44 views

Regular expressions

I am new to theoretical cs and am working through it slowly. I have completed a simple question and was wondering if my answer is correct or not. Thank you kindly for any feedback. The question is: ...
1
vote
2answers
62 views

Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?

For example, a valid number would be 6165156 and an invalid number would be 1566515. I have tried many times to construct a finite state machine for this with no success, which leads me to believe the ...
0
votes
1answer
99 views

CFG-Infinite recursion

As you see, the string production process never ends. Can someone explain me if this language is regular or not ? $ S \to Α Β S $ $ A \to S $ $ B \to a B b $
2
votes
1answer
45 views

Pumping Lemma,regular languages

Lets say that we have the language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $>=0$ } What is the way that i should follow to prove that the language is not regular? Assume that the language is ...
0
votes
1answer
33 views

validation of a pumping lemma proof for regular languages

I have the following regular expression: Of course I could think of a word 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 ...
0
votes
1answer
27 views

What is Pumping length for Union of Regular languages?

This is an exam question. For E = {a,b}. let us consider the regular language $L= \{x|x = a^{2+3k} or x=b^{10+12k}, k >= 0\}$ Which one of the following can be a pumping length (the constant ...
0
votes
0answers
25 views

I can't seem to convert a NFA to a regex. What am I doing wrong? [duplicate]

I have the following diagram : I try to remove state 3: Now I do this: What do I do now to get my regular expression? I'm stuck.
4
votes
1answer
261 views

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), ...
0
votes
1answer
28 views

Convert the given NFA to DFA

I am trying to find an DFA for the regular language given by the expression $L\left( aa^{\ast }\left( a+b\right) \right)$. First simplifying $L\left( aa^{\ast }\left( a+b\right) \right)$ we get $L\...
-1
votes
1answer
37 views

Turing Machine construction of M=wwRw form

Construct a Turing machine for M = {wvw| v, w ∈ {a, b}*, reversal(v) = w}. I tried to imagine that I will have to divide the string into 3 equal parts and check if ...
1
vote
1answer
25 views

Is regex with backreference still able to be implemented by finite automata?

I recently learned that regex support backreference which enables referring to a matched group in the pattern itself. E.g. a regex (.)\1{2,} matches two or more ...
-1
votes
1answer
21 views

How can I prove that the accepted language of a given DFA or NFA or REGEX is equivalent to a given language

I found this How do I verify that a DFA is equivalent to a NFA? but as it states it is not really a good question more of how can I check myself during an exam. Because as you might know to do this by ...
-3
votes
1answer
38 views

Construct regular expression for given language

How to construct regular expression for language L={a,b,c} which contain all words starts with bab and ends with babc?
0
votes
0answers
51 views

Does the order of ripping off the states matter?

Do we get same regular expressions at the end regardless of the order that we take the states step by step? Can somebody prove by exemplification?
3
votes
1answer
117 views

Why is this language a regular language?

Came across this in a book, and I'm wondering why the following language is regular? $$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$ Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a ...
0
votes
2answers
47 views

Regular expression for a palindrome of finite length?

I have a language $$ L = \{ww^R, w \in \{ab\}^5\}$$ I know this is a regular language because it is finite (since w can only be of length 5). I want to prove it's a regular language, so I'd create a ...
1
vote
1answer
37 views

How to create a regular expression for this language?

I have a language: $$ \{a^jb^k \mid j \neq k \text{ and } j \equiv k \pmod 3 \}$$ I want to prove that this language is regular. My first thought was to create a regular expression that accounts for ...
1
vote
1answer
68 views

RE Construction: Strings of even length in alphabet {a,b,c} that contain exactly one a

i am reviewing older exams from my computational theories lesson in university and i am struggling to figure this one out: Construct a regular expression for the following language: Strings of even ...
28
votes
11answers
4k views

Unusual applications of regular expressions?

I am looking for some interesting applications of regular expressions. Can you name any unusual, or unobvious, cases where regexes find their application?
1
vote
1answer
36 views

Construct regular expression that contains the substring

I need to write a regular expression for the following set of strings on Σ = {a, b, c} in which the number of b’s is even, and contains abcba as a substring. So far, the even number of b's can be ...
0
votes
0answers
46 views

Construct a DFA with reduced states equivalent to 10 + (0 + 11)0*1

I have found this question in a book. I could convert it into its equivalent DFA. But the problem is with the "reduced state" part. I think the answer given in the book is wrong. What would be the DFA ...
0
votes
2answers
37 views

convert RE to NFA

The Regular Expression i am having trouble with is the following a(b|bcc*)*c. My main concern is what do i do with the c*? I can lay the rest of the diagram correctly (i think) but that part is ...
2
votes
2answers
39 views

Proving non-regular language using the pumping lemma

I would like to verify that the following language is not regular. I know that if the pumping lemma is not valid then the language is not regular. (but its not enough to prove that the language is in ...
1
vote
2answers
313 views

Over the alphabet {a,b,c,d}, how would i construct a NFA that only accepts strings that end with a letter that is already part of the string?

I've been trying to create a NFA that accepts strings that end with a letter that exists in the string. For example abcdb, cbdd, acac etc. while strings like abc aacd etc are not accepted since the ...
-1
votes
2answers
346 views

Regular expression without 00 as a substring

I want to create a regular expression for the language: $L=\{w \in \{0,1\}\mid w \text{ does not contain 00 as a substring}\}.$ I've tried various things, but I can't seem to get the correct regular ...
2
votes
3answers
123 views

An approach to determine whether language is regular or not?

I have the following problem. I need to determine whether this language is regular or not: $L:= \{ w \in \Sigma^*: \forall \alpha ∈ \Sigma, |w|_\alpha \text{ is even or divisible by 3}\}$ $|w|_\...
0
votes
1answer
35 views

Is this a valid DFA for (a|b)*abb?

I'm trying to come up with an alternate DFA for accepting (a|b)*abb than the one present in the dragon book. Here's the one I tried: It seems valid to me but I'm ...
0
votes
0answers
12 views

How to write regular expression [duplicate]

The set of all strings over {0,1} such that every block of 4 consecutive symbol contain at least two 0's Can you guys tell me what is the correct answer for this ?
1
vote
0answers
15 views

Regex vs line by line read efficiency - general concept question

Say, I have a file that is somewhere between 10-20 pages long. I need to extract 10-20 pieces of information from it that I can fairly easily extract using a series of regex-es or by running code that ...

1
2 3 4 5
13