1
vote
2answers
20 views

A question about operations on languages.

I come across this problem on a book. It states that: for languages A and B, $(A\cup B)^* = (A^*B^*)^*$. I know that the definition of star closure is $\left(\bigcup^{\infty}_{i=1}\right)A^i$. But so ...
0
votes
2answers
316 views

Regular expression and DFA/NFA questions

If a language L is generated by a regular expression, then L is recognized by a DFA. I think this is true, because regular expressions describe regular languages, those of which are exactly ...
0
votes
1answer
69 views

Finding regular expressions

I'm given the DFA shown below and need to find regular expressions for the following languages: $L_{1,2}^0, L_{2,1}^6, L_{2,5}^4, L_{2,3}^5, L_{1,3}^5$. The language $L_{p,q}^r$ is defined as ...
1
vote
0answers
35 views

Constructing a Turing decidable machine from DFA

I am a trying to prove that every regular language is decidable. So in order to prove that I am trying to show that I can move from deterministic finite automaton (DFA) to a Turing decidable machine. ...
1
vote
1answer
57 views

Working with the word w⋅y, while given the word y⋅w

$L$ is a regular language. I am given $F(L)$ such that $$F(L)= \{wy \mid yw\in L\}$$ I need to prove that if $L$ belongs to $L_\text{dfa}$, $F(L)$ also belongs to $L_\text{dfa}$. I am having a hard ...
1
vote
2answers
285 views

Constructing a finite automata from a subset of its language

I am attempting to solve the following problem: Let $M=(Q,\Sigma,\delta,q_0,F)$ be a deterministic finite automata which accepts $L(M)$, and let $E$ be the subset of $L(M)$ consisting of all words of ...
1
vote
1answer
166 views

Prove that if $ L $ is a regular language over the alphabet $ Z = \{ 0,1 \} $, then $ L' = \{ax \mid x \in L \} $ is also regular for any a in $Z$.

Prove that if $L$ is a regular language over the alphabet $Z = \{0,1\}$, then $L' = \{ax \mid x \in L\}$ is also regular for any $a \in Z$. I'm not sure how to even begin on this one. If even a ...
2
votes
2answers
111 views

Basic regular expressions problem

I'm in an intro to CS theory class learning about regular expressions. I was wondering if people could give me hints as to whether I'm on the right track for these problems. I hope this particular ...
1
vote
2answers
624 views

How to prove by pumping lemma these languages are not regular?

$L_1 = (a^k * b^r \mid k \neq r^2)$ $L_2 = (a ^{\sum_i ^n t} \mid n > 0 )$
0
votes
1answer
196 views

Building a regular grammar from NFA

I'm requested to make a regular grammar from a given NFA. In this NFA, there's a "death state", which means, when getting to it, there's no way back to the rest of the states (a self-loop to the same ...
1
vote
1answer
72 views

Proving or disproving regularity of a language

The question is as follows: If L1 and L2 are not regular and L1 ⊆ L ⊆ L2, then L is regular My intuition says that it's wrong so I've been looking for a ...
0
votes
2answers
96 views

following languages regular or not?

Please help me determine if those languages are regular or not. If not, I'll be glad to get a direction to prove it by contraditiction of the pumping lemma: $L = \{a^n\mathord{*} a^m \mid m \equiv ...
0
votes
1answer
38 views

proving by construction that language is regular

I had this exercise saying the following: $$ L =\{w\mid w = w_1xw_2 \land w_1, w_2, x\text{ are words }\land w_1w_2 \in L_1 \land x \in L_2\} $$ I need to prove that $L$ is regular by defining an ...
2
votes
0answers
279 views

Regular, Context-free, Recursive, Recursively Enumerable Language Relationships

I am currently under the believe that all regular languages are context free, thus all regular languages are recursive, and therefore all regular languages are recursively enumerable. If I am given ...
0
votes
3answers
101 views

showing that a regular language is regular after taking a letter off or after adding letters

I'll be happy to recieve help with this one: Given the regular language $L$ defined over alphabet $\{a,b\}$, show that the following languages are also regular: $\{xy\mid xay\in L\}$ ...
0
votes
1answer
621 views

Formal proof of the concatenation of two regular languages automaton

During an exercise for college, given two NFA's, $A_1\text{ and }A_2$ that accept the languages $L_1\text{ and }L_2$, I've built a NFA, $M$ that accepts the language $L_1*L_2$ (concatenation). The ...
0
votes
2answers
131 views

Help with regular expression subset proof

Okay, so basically I'm just showing that two ways to express a regular expression are equal, and to do so, I'm showing they're subsets of each other. The expression is: $(A^*B^*)^* \subset ...
0
votes
1answer
209 views

Homework proof Extended Transition Function by mathematical induction

Let M = (Q,∑, q0,A, δ) be an FA. Below are other conceivable methods of defining the extended transition function δ∗. In each case, determine whether it is in fact a valid definition of a function on ...
6
votes
1answer
103 views

Existence of NFA for this language

I'm given a task to find (and prove) such language $L$ in the alphabet $\Sigma = \{a,b\}$ with all words less than $1000$ in length, for which any DFA/NFA will have more than $10^{10}$ of states. For ...
3
votes
2answers
123 views

Creating a regular grammar

Hi I am trying to write a grammar for $L=\{xcy \mid x \neq y^R \land x,y \in \{a,b\}^*\}$. I am not able to think beyond a point as to how to write the grammar. Could someone guide me?
1
vote
2answers
204 views

Prove that [ContextFreeLanguage - RegularLanguage] is always a context free language, but the opposite is false

Let L be a context-free grammar and R a regular language. Show that L-R is always context-free, but R-L is not. Hint: try to connect both automata) The above hint did not help me :(
1
vote
1answer
352 views

Algorithm to tell whether a regular language contains at least n strings

I'm taking a course on formal languages and was given this exercise: Give an algorithm to tell whether a regular language $L$ contains at least $100$ strings. Can someone give me a hint? Thanks! ...