Tagged Questions

Regular expressions or Regex is a search pattern for strings defined by a sequence of characters.

362 views

60 views

Write the regular expression of the language that the DFA accepts.

I am given a DFA and I have tried to write the regular expression of the language that it accepts. This is the DFA that I am given: I have found some words that the DFA accepts: ...
465 views

A regular expression for the words that don't contain the sequence $ab$ over $\{a,b,c\}$

The following is an exercise in a book I am reading: Let $\Sigma=\{a,b,c\}$, define $L$ to be the language of all words over $\Sigma$ that do not contain $ab$ as a sub-word. Find a regular ...
114 views

Number of sequences that contain a given “run”

Consider sequences of numbers 0, 1, 2 with length n. There are $3^n$ such sequences. I want to know how many sequences there are that contain a k-run of 1's followed by 2. As a regular expression: ...
51 views

Give a regular expression for $A = \{1^{k}y|k \geq 1, y \in \{0,1\}^{*}$ and $y$ contains at least $k$ $1$'s $\}$

The regular expression that is given is $1(0 \cup 1)^{*}10^{*}$. I'm having trouble realizing why this regular expression describes the language given. For example, the string (for $k$ = 4) $1111$ ...
40 views

Proving that the language $\mathscr L$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{\text{all the binary words such that the number of ones divide the number of zeros}\}$ is non regular using the pumping lemma For example: ...
Determine whether $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ is regular.
Given the alphabet $\Sigma=\{a, b\}$ and for the next Language $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ determine whether the language is regular. Firstly, I think this language is regular. ...