The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
2answers
346 views

Converting from NFA to a regular expression.

This is a NFA, I have been working to covert it to a regular expression. After I'am done, I arrive at an expression as follows $$ \left(((a\cup b)a^*b) (ba^*b)^*a\right)^* \left(((a\cup b)a^*b) ...
0
votes
2answers
68 views

Regular expression 00 or 11 not both

Can anyone help me with this question: I know it before, but I have tried to solve it myself and didnt succeed. what is the regular expression for this language: L=all words that have 00 or 11 but not ...
1
vote
1answer
689 views

induction proof for kleene star

i am going through some past exam paper questions on regular languages for some revision, and i am having a bit of trouble with converting general ideas into formal mathematical proofs. the question ...
1
vote
2answers
126 views

Formal Languages - Regular Expression

I've been battling the following two questions for more than a day today. Write a regular expression (comprised of {a, b}) that contain at least two b and do not contain abb. Write a regular ...
1
vote
3answers
291 views

Draw a finite state machine which will accept the regular expression $(a^2)^* + (b^3)^*$

Draw a finite state machine which will accept the regular expression: $(a^2)^* + (b^3)^*$ In particular, I am confused by the $+$ sign, what does it exactly mean? Most literature I could find about ...
0
votes
1answer
55 views

Drawing automata for languages

I'm trying to draw two automata for these two languages: For the first one, I know that the minimum is n = 1, m = 1, but I'm having troubles drawing a NFA for it. The second one the minimum is n = ...
1
vote
1answer
33 views

Is $L_1$ context free language?

Let $L = L_1 \cap L_2 $, where $L_1$ and $L_2$ are languages as defined below: $L_1= \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ $L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$ Then L ...
1
vote
1answer
444 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 ...
4
votes
1answer
62 views

Proving that all equivalent regular expressions are reachable via algebraic laws

Given a set of laws for regular expressions, for example (ripped from this document): $$ \begin{array}{llll} \text{1.} & (A|B)|C = A|(B|C) &\qquad& \text{(associativity of choice)}\\ ...
1
vote
1answer
58 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: ...
0
votes
1answer
33 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: ...
0
votes
2answers
66 views

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. ...
1
vote
1answer
46 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$ ...
0
votes
1answer
27 views

Regular expression for language containing all strings that start and end with different symbols

ques - Regular expression for language containing all strings that start and end with different symbols i just went through some examples where the RE for above question is ...