Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
28 views

Regular language question [closed]

It have been stated that every language has a regular superset Σ∗ . Now if Σ∗ is regular than it means regular language must be the greatest language than all other's chomsky classifications grammars. ...
2
votes
1answer
520 views

How do I convert the following GNFA to regular expression?

Here is a GNFA I made from an NFA. I'm unsure how to treat the node of b(a∪b)* (the first node after the start node and the one below it). Since it doesn't lead to any goal state, do I disregard it ...
2
votes
2answers
1k views

Language of all strings that has exactly 1 triple b

I am new to automata and learning to make regular expression for languages. But I have been stuck on this one. Suppose we have a language L, Language of all strings that has exactly 1 triple “b” ...
1
vote
1answer
67 views

Converting DFA to Regular Expression Using State Removal

I'm trying to convert the following NFA to a regular expression. I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been ...
1
vote
2answers
54 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
25 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\...
0
votes
1answer
87 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
36 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
32 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
20 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.
0
votes
1answer
42 views

Product of Lexical Specification

I have a problem that asks me to consider the string abbbaacc. I'm supposed to figure out which of the following lexical specification produces the tokenization ab/bb/a/acc. The options are: ...
4
votes
1answer
236 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), ...
2
votes
2answers
2k views

DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)?

Our class teacher gave us a descriptive definition of a language in a Quiz today and ask us to make its DFA. In the middle of quiz he also told us the Regular Expression(RE) of that language but we ...
-1
votes
1answer
27 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
22 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
20 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
36 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
2answers
181 views

What is the deterministic finitite automaton (DFA) for the regex “.*b.”

I'm looking for a finite state machine that can match inputs to the regular expression .*b. deterministically (i.e. it cannot change state w/o being fed input and ...
0
votes
0answers
49 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?
1
vote
1answer
28 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
2answers
41 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 ...
3
votes
1answer
111 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 ...
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
2answers
118 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
vote
1answer
57 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?
3
votes
3answers
84 views

Regular expression for language that does not accept x string (3 letters, |x|=3)

The language I am interested in is $L=\{w∈\{a,b,c\}^*| w$ contains "$bac$" but not "$cab$"$\}$. I am thinking that the result will have the form $L=X_1X_2X_3$, where $X_1=\{w∈\{a,b,c\}^*| w$ does not ...
0
votes
0answers
19 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
37 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
votes
2answers
72 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 ...
0
votes
1answer
47 views

Regular expression and Right Regular grammar for decimals starting with 1 ending with 9?

I was trying to do the following: Consider the set of all strings over the alphabet {0,1,2,9} that are decimal numbers beginning with 1 and ending with 9 and having exactly one decimal point (.). ...
4
votes
2answers
383 views

Using Brzozowski's derivatives method to construct a minimal DFA

so I am currently learning about dfa and nfa and i came across the following question which requires me to use Brzozowski's derivatives method to construct a minimal DFA recognizing the language ...
2
votes
3answers
112 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
31 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 ...
1
vote
1answer
2k views

How to convert DFA to regex with State Elimination

I can do the very simple transitions but it gets difficult when you have transitions jumping over 1 or more states. I have this difficult DFA i need help converting to RE: using STATE ELIMINATION ...
1
vote
3answers
162 views

Large DFA to regex?

For an assignment for one of my courses, one of the questions is to provide a regular expression for the language: "the set of strings such that the number of 0’s is divisible by six, and the number ...
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
14 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 ...
0
votes
0answers
43 views

Regular grammars

I am fairly new to automata, regular expressions and regular grammar. I am struggling to understand how to define the regular expression (abc)* into one or several regular grammar expressions. ...
0
votes
0answers
50 views

McNaughton-Yamada Algotihm (1960) Regular Expression to DFA without passing through NFA

I have a homework problem here. It asks me to use the McNaughton-Yamada algorithm to first convert a regular expression to a DFA, and then minimize this using a partition argument. I can do the latter....
3
votes
1answer
97 views

Arden's Rule, DFA & NFA to regular expressions

I have been trying to figure out the Arden's Rule and the equational method to transform DFA's & NFA's to RE. I know what the rule state: if x = s + xr then x = sr*, with $s,r\in$ Regular ...
2
votes
2answers
61 views

regex of three repeating number

I need a regular expression, not one using coding syntax, to write an expression that has a vocabulary of 1,2,3 and every string in the language has at most one occurrence of the substring 222 but ...
1
vote
2answers
85 views

Prove the following language is regular?

Assume $L_1$ is a regular language, and define: $$L = \{wcv ∈ \{a, b, c\}^* \mid |w|_a + 2|v|_b ≡ 3 \bmod 5, w, v ∈ L_1\}.$$ Show that $L$ is regular. I first tried to prove by showing that the ...
1
vote
1answer
46 views

Are these REs equivalent?

I have to implement a compiler for a given language as part of an assignment. The language is kept simple enough such that it can be fully expressed through REs. My question lies with two of the REs ...
0
votes
2answers
59 views

Generating regular expressions not containing abc

Let sigma = {a,b,c}. How do I generate a language L that does not containg abc? Any guidance is appreciated!
3
votes
4answers
10k views

Regular expression for a binary string containing even number of 0's

To get the regular expression I made a finite automata as the following (not sure if you can directly write regular expression without it): The regular expression for the above according to me ...
1
vote
1answer
25 views

How to describe the languages of these regular expressions in plain English?

This is actually a question my lecturer gave us, so I know that it's kind of homework, but I tried to answer this and still had no luck. The question is Give English description of the languages ...
0
votes
0answers
30 views

How to write a regular expression that excludes certain strings? [duplicate]

It's a homework problem. Assume $\Sigma = \{a ,b\}$, I am asked to construct a regular expression that does not have both the substrings bba and abb. My idea was: construct a regex that matches ...

1
2 3 4 5
13