Tagged Questions

Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.

60 views

If $A$ is regular, is the language $\{x \;\mid\; \exists y : |y| = |x|^2, xy \in A\}$ regular?

Here is the question: Let $A$ be any regular set over some alphabet $\Sigma$. Is the language $$L = \{x \;\mid\; \exists y : |y| = |x|^2, xy \in A\}$$ necessarily regular? I am unable to ...
63 views

Converting Automata To Regular Expression Using State Removal Method

From the following automaton this solution is given: $$(a\mid b)^*aa(ba)^*a(a\mid b)^*$$ But when I try to convert this automaton into a regular expression I always end up with the wrong ...
23 views

How to prove non-regularity of a language from the non-regularity of another language?

How can I prove that $L_1=\{a^nb^m\mid n\ne m\}$ is not regular based on the fact that the language $L_2=\{a^nb^n\mid n\in\Bbb N\}$ is not regular? Thank you
47 views

29 views

How to prove that a simple NFA is minimal, without any algorithm?

First, I will present the question I was doing: We will define $p(L)$ to be the minimal natural number so that a language L fulfill the pumping lemma. We will also define $n(L)$ to be the minimal NFA ...
20 views

Do the initial segments of the strings of a regular language form a regular language?

Let's say you have a set of strings $R$. A string $s$ is part of my language $S$ iff there is a string $r \in R$ such that $s$ is an initial segment of $r$ (you can get $s$ by removing characters from ...
27 views

Is the resulting language regular?

If $L$ is a regular language then is $L'=\{w \mid wx \in L \text{ for some string }x\}$ regular? First step is understand $L'$. So it is a subset of $L$ that contains strings with a certain prefix?
33 views

Cocke-Younger-Kasami (CYK) Proving a word is in a language

Using CYK algorithm I need to figure out whether the word abbabb is a word of the language of the following grammar. I think I have completed the problem correctly but I'm not sure, I'm hoping ...
200 views

What does arbitrary number mean?

A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits). Is it true ? My attempt : Arbitrary length means variable length, and there ...
25 views

Identify the class of language?

Given a set $$S=\{x∣ \text{there is an x-block of 5's in the decimal expansion of π}\}$$ (Note: x-block is a maximal block of x successive 5's). Identify class of language? Somewhere it ...
41 views

23 views

Proving that the language $\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma My try: $\{a,b\}^*=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,\dots\}$ ...
129 views

Read-only Turing machine recognizes only regular languages?

Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages. According to wiki : A read-only Turing machine or ...
38 views

Writing a regular expertion for the language $L=\{0^n1^m \mid n\equiv m\pmod 2\}$

I need to write a regular expertion for the language of all the binary words that contains continuum of even number of zeros and after that even number of ones or odd number of zeros and after that ...
12 views

Language of all the binary words that not contains continuum of more then $3$ zeros

I need to write a regular expertion for the language of all the binary words that not contains continuum of more then $3$ zeros, for example $0011110100\in L,\,\,\,\,\,\,\,\,\,11000001100\notin L$ ...
26 views

30 views

$L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$ is regular?

Given language : $L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$ is regular? Somewhere it explained as : Here we need just 6 states ...
15 views

Proof of L being a regular languaje

I have the following language $$L = \{w\in\{a,\;b\}^* : a^nv,\; n\geq 1 \wedge |v|_a \geq n\}$$ Formed by characters "$a$" and "$b$" where the word $v$ has more "$a$" characters than $a^n$. I have ...
231 views

Automata | Prove that if $L$ is regular than $half(L)$ is regular too

I've see couple of approaches to this kind of questions yet I have no clue how to approach this one. Let L be regular language, and let half(L) be: $half(L) = \{u | uv \in L\ s.t. |u|=|v|\}$ Prove ...
35 views

Regular expression language that describes a graph?

Does anyone know of a regular expression language that can be used to describe a chart with time on the x-axis and price on the y-axis? I would use this language to match regular expressions against ...
21 views