Linked Questions

0
votes
1answer
196 views

Simple regular expression problem [duplicate]

new to automata theory and this is quite difficult for me so I'd appreciate a hint in the right direction if possible. We want to find a regular expression for the language $L$ over $\Sigma = {a,b,c}$...
0
votes
0answers
240 views

Regular expression for set of strings with no two consecutive 1's? [duplicate]

I'm having trouble figuring out a regular expression over the alphabet {0,1} that contains all strings with no TWO consecutive 1's. I'm also wondering if there is a pattern that could be extended to ...
0
votes
0answers
158 views

Regular expressions for words avoiding aaa,bbb,ccc [duplicate]

I need to write a regular expression for all words over $\{a,b,c\}$ not containing $aaa$, $bbb$ or $ccc$. Will appreciate any help. Note: this is not homework.
-3
votes
1answer
105 views

Step by step method for generating Regular Expressions for languages [duplicate]

I was wondering if there was a method that can be used to generate a Regular Expression for a language. Take the Language $L$ as an example where: $L= \{w \in \{0, 1\}^{\ast} \mid \text{length of } w ...
0
votes
1answer
83 views

What is the regular expression of this language? [duplicate]

$\Sigma = \{0, 1\}$ $L = \{x$| $x \in \Sigma^* $ $\&$ $ \#_0(x) = 3$ $or$ $ \#_1(x) = 3 \}$ What is the regular expression of this language? At first I thought $r = (0+1)^*0(0+1)^*0(0+1)^*0$ $...
-1
votes
1answer
42 views

Give regular expression on language [duplicate]

What is a regular expression for $L_1=\{a^{2n} b^{3m+1} \mid n \geq 1, m \geq 0\}$?
0
votes
0answers
37 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 ...
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 ?
-2
votes
1answer
12 views

Regular expressions for some languages [duplicate]

Set of strings over $\{0,1\}$ having at least two occurrence of the substring 00. $\{a^n b^m : n ≥ 4, m ≥ 3\}$. Set of strings over the alphabet $\{a,b,c\}$ containing at least one $a$ and one $b$.
125
votes
4answers
175k views

How to convert finite automata to regular expressions?

Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
50
votes
8answers
87k views

How to prove a language is regular?

There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular? For instance, if I am given that $L$ is regular, how can I prove that ...
4
votes
3answers
7k views

Write a regular expression - Contains an equal number of 01 and 10 subtrings

I'm trying to write a regular expression for the language $L\subseteq\{0,1\}^*$ of strings that begin with $0$ and contain an equal number of occurrences of the substrings $01$ and $10$. ...
0
votes
3answers
6k views

DFA for Strings with third symbol from RHS as 1

How can we make a DFA for given condition in title from alphabets {0,1} (binary). What can be the regular expression for this? My calculated expression is (a+b)*a(a+b)(a+b) , please correct me if i'...
1
vote
1answer
2k views

Regular expression for words in a language where each letter appears at least once

What is a regular expression or finite automaton that will accept words in the alphabet $\{a,b,c \}$ where each letter appears at least once? Acceptable words: $ abc, cba, cbcbcba, abbbcaabb$ ...
1
vote
1answer
1k views

Regular expression - every b preceded and followed by an even number of a's

I'm trying to write a regular expression over the alphabet $\{a, b\}$ for the language in which every $b$ is preceded and followed by an even number of $a$'s. I think the regular expression should ...

15 30 50 per page