Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

-2
votes
1answer
13 views

Can every recursively enumerable language be defined with regular expression?

Can every recursively enumerable language be defined with regular expression? I came across this question, when studying for my test: Prove that for any finite language $L$, there is a Turing machine ...
3
votes
1answer
139 views

How to proof that a language is not recursively enumerable

How does one prove that some arbitrary language $L$ is not recursively enumerable. I know I can proof that language $L$ is recursively enumerable by constructing a Turing machine $M$ that accepts all ...
0
votes
1answer
38 views

Pumping Lemma for $L=\{a^{2k} b^n b^k \mid k\ge0, n\ge0\}$

$L=\{a^{2k}b^nb^k\mid k\geq0, n\geq0\}$ over alphabet $\{a,b\}$ How do I prove that $L$ is not regular using Pumping Lemma? All the examples I've come across had same exponents all around, and I'm a ...
0
votes
2answers
39 views

High Level Explanation of the Pumping Lemma

I have a problem that I cannot figure out regarding using the pumping lemma to prove that a language is not regular. I don't understand how I go about proving through contradiction that the language ...
-1
votes
0answers
10 views

Prove L is regular of the language L^R [duplicate]

for L^R = {w^R|w E L} prove L is regular, then so is L^R.
3
votes
2answers
221 views

complexity of determining whether a language given by context free grammar is empty

I know that it is decidable problem to check whether given context free grammar represents empty language -- for instance, AFAIR one could convert it to Chomsky normal form, and then check if any word ...
0
votes
1answer
18 views

What is the purpose of $\epsilon$ transition?

$A = \{a^i b^j c^k\mid i = j\text{ or } j = k; i, j, k \ge 0\}$. In its push down automaton should not there be the red colored transition instead of the black colored one?
1
vote
0answers
24 views

Is “duplicate” in RPN enough for replacing variable binding in term expressions?

I try to work out some consequences of storing (or "communicating"/"transmitting") a rational number by a term expression using the following operators: $0$, $\mathsf{inc}$, $\mathsf{add}$, ...
0
votes
1answer
37 views

LR(0) expressive power

So I have grouped the following formalisms into a power hierarchy (and made classes for them): Class 1 DFA NFA NFAϵ reg.exp Class 2 (DCFL expressivity?) LR(1) DPDA Class 3 CFG PDA Class 4 ...
3
votes
2answers
61 views

If $L$ is regular, must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular?

The reverse, $w^{R}$, of a string $w = w_1w_2...w_n$ is the string $w_n...w_2w_1$. Suppose that L is a regular language. Must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be ...
0
votes
1answer
56 views

Intersections of some context-free languages

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
3
votes
2answers
68 views

Give an example of a language whose Myhill-Nerode equivalence relation is such that if $x,y \in \{0,1\}^*$ with $x \neq y$, then $[x] \neq [y]$

Suppose $\Sigma = \{0,1\}$. Provide an example of a language $L \subseteq \Sigma^*$ with the property that its associated Myhill-Nerode equivalence relation, $R_L$, is such that every one of its ...
-1
votes
0answers
22 views

Prove Regular Language and Reversal [duplicate]

I'm being asked to prove the following: Given a regular language $L$, prove that the collection of strings in $L$ whose reversals are also in $L$ is regular. So, for example, given $L = \{ab, ...
3
votes
1answer
55 views

Showing that A' is a regular language

Let $\Sigma = \{0,1\}$, and suppose that $A$ is a regular language. Define $$A' = \{ u \mid \exists a, b \in\Sigma: abu \in A\}$$ i.e., $A'$ is obtained from $A$ by taking every string in $A$ and ...
-1
votes
1answer
34 views

Equivalence of some Automata & Language & NFA

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
2
votes
1answer
64 views

Is there a class of formal grammars that generate Recursive Languages only?

Is there a class of formal grammars that generate Recursive Languages only? (ie with which it is not possible to generate non recursive languages.) If so what kind of production rules/restrictions do ...
3
votes
2answers
431 views

If both the concatenation of two languages and the second “half” are regular, is the first too?

Given that $L_2$ is regular and infinite and $L_1 \cdot L_2$ is regular, then $L_1$ is also regular. I need some help on getting started on proving this is the case. My intuition is that if $L_1 ...
2
votes
2answers
71 views

Prove that the equal-length concatenation of regular languages is context free

If A and B are regular, then prove that $A@B = \{xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y|\}$ is always context free. So I'm trying to come up with the proof that looks something like ...
1
vote
2answers
64 views

Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final states

Just as the question asks, I am trying to understand the relationship between the number of accept states a DFA has (not necessarily the total number of states) and the languages it can accept. I ...
2
votes
1answer
114 views

Are DCFLs closed under reversal?

According to this chart, DCFLs are closed under reversal. However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and ...
0
votes
2answers
67 views

Finding context free grammar for this language?

I needed help finding the context free grammar of this string $$ 10^{n}10^{n}1 $$ So far an idea I have is $$ S\rightarrow 1S1S1\mid 0S \mid \varepsilon $$ Any assistance you can provide would be ...
12
votes
6answers
2k views

What is the Relationship Between Programming Languages, Regular Expressions and Formal Languages

I've looked around the net for an answer to this question and it seems as if everybody implicitly knows the answer except me. Presumably this is because the only people who care are those who have had ...
0
votes
1answer
84 views

Decidability of a language of Turing Machine descriptions [duplicate]

Given the language $\{ <M> \mid\:$ M is a Turing machine and there is some w ∈ Σ* for which the computation M(w) takes more than 10 transitions$\}$ How can one prove that this ...
3
votes
1answer
99 views

Why does this pumping lemma application “prove” that 0*1* is not regular?

Here is a proof that $0^*1^*$ is not regular, even though it is regular. I'm having a hard time figuring out what is wrong with the proof. Assume $0^*1^*$ is regular. Let $p$ be the pumping length as ...
1
vote
1answer
94 views

Can $\{a^mb^nc^n\mid m,n \ge 1\}$ be proved non-regular using the pumping lemma?

$\{a^mb^nc^n\mid m,n \ge 1\}$ intuitively seems like a non-regular language. It looks like the machine needs to remember the number of $b$s (which isn't limited). The pumping lemma can be used to ...
0
votes
1answer
38 views

DFA for every run of a's=2 or 3

I am trying to create a dfa for L={w: every run of a's has length either two or three} this is my attempt at the solution..i feel like I am missing something..?
0
votes
1answer
36 views

Find strings in L^4

Let L = {ab,aa,baa}. I need to find L^4. From my understanding, I union the set. So: ...
8
votes
3answers
810 views

Union of regular languages that is not regular

I've come across that question : "Give examples of two regular languages which their union doesn't output a regular language. " This is pretty shocking to me because I believe that regular languages ...
-1
votes
0answers
55 views

Theory of computation - Proving that a language is non-regular [closed]

I learned about the Pumping Lemma in class a couple of lectures ago, and after reading my book/other sources online I think I have come to understand it. I am doing sample exercises like the one ...
0
votes
2answers
80 views

What does it mean to prove that a set of binary integers is regular?

I'm not exactly sure what this question is asking me to do: Show that the set of binary integers (given as strings over $\{0, 1\}$) that are divisible by $3$ is regular, by giving a DFA that ...
2
votes
2answers
86 views

Prove that REG is closed against removing all but lexicographicaly largest words (per length)

Let $\Sigma_n = \{0, 1, ... , n-1\}$. Suppose $L \subseteq$ $\Sigma^*_n$, and let $\qquad\displaystyle\mathcal{B}(L) = \{ x \in L : x = \textrm{lex}\max L_m, m \in \mathbb{N}_0 \}$, ...
-3
votes
0answers
28 views

Complement of $\{\langle M\rangle\mid M \text{ enters state q5 for the input string } 101\}$

Let language $L_1 = \{\langle M\rangle\mid M \text{ enters state q5 for the input string }101\}$. Would the complement of the language $L_1$ be $$\{M \text{ does not enter the state q5 for the ...
0
votes
2answers
56 views

Does the complement of sigma Kleene star exist?

If $\Sigma^*$ is the set of ALL strings including the empty string, then what can its complement possibly be? The empty set?
1
vote
1answer
74 views

Grammar for ${a^n b^n c^{n+m}}$

Can we define a grammar for the following language? $$L = \{a^n b^n c^{n+m} | n,m>=0\}\,. $$ I can define one for this: $$L=\{a^nb^n|n,m>=0\} $$ S --> aSb | λ or this one: ...
2
votes
0answers
30 views

Tree Languages are Word Languages on an Infinite Alphabet of Contexts

I have been reading the book Tata (Tree Automata Techniques and Applications), and there is a sentence I have read thousands of times, yet still don't quite understand. In the beginning of Chapter 2, ...
4
votes
0answers
34 views

Languages recognized by finite state automata of polynomially growing size

In the course of my research (condensed matter physics stuff), I stumbled over the following concept: The class of regular languages can be defined via finite state machines (FSM): A language $L$ ...
0
votes
2answers
34 views

help understanding formal grammar for subtraction example

I am going through the following document trying to understand a simple grammar for a basic subtraction example (page 4). The example states that Simple arithmetic expressions of arbitrary length ...
1
vote
0answers
16 views

examples of strings that is not in the set [closed]

I'm kind of struggling with finding a string that is not in this set {w: for some u ∈ Σ*, www = uu} where Σ = {a,b} from what I understand, the set of Σ* is, {E, a, b,aa, ab, ba, bb, aaa, ...} if w ...
2
votes
1answer
83 views

Prove that the language is not regular without using Pumping Lemma

I am practising problems on Regular Languages and I came across this question: Prove that the language $$\{a^m b^n : m ≥ 0, n ≥ 0, m \ne n\}$$ is not regular. (Using the pumping lemma for this ...
0
votes
2answers
60 views

Creating a grammar from the language

L = { a^n b^2n a^(n+2) : n>=1 } So I'm trying to construct the grammar and I'm getting stuck.Some example strings would be these (spaced out to help demonstrate the patterns): a bb aaa aa bbbb aaaa ...
0
votes
1answer
37 views

NFA state complexity for the complement of EPAL restricted to a fixed length

I've been having trouble proving the next statement: Let $L_n=\{ww, |w|=n\}$ (the set of equal-length palindromes (EPAL) restricted to length $2n$). Prove that $L^c_n$ can be accepted by an NFA ...
-2
votes
1answer
35 views

Prove that $(L^*M^*)^* = (L\cup M)^*$

I would like to find out how to prove this statement. Thank you. Well I think that I proved one part of the statement, but my proof doesn't really look elegant. My proof of $(L\cup M)^* \subset ...
9
votes
1answer
247 views

Constructing all context-free languages from a set of base languages and closure properties?

One way of looking at regular expressions is as a constructive proof of the following fact: it's possible to construct the regular languages by starting with a small set of languages and combining ...
1
vote
1answer
61 views

Don't understand closure under string reversal

I am trying to learn from http://www.cs.uiuc.edu/class/su08/cs273/lectures/lect_06.pdf #2 and I understand everything except for the 2nd line of delta prime prime function, I having breaking down ...
4
votes
2answers
87 views

Kleene closure of the empty set

In the book introduction to automata theory and languages, $L^*$ is defined as $$L^* = \bigcup_{i=0}^\infty L^i $$ The book also says that $\emptyset^* = \{ \epsilon \}$. But since $\emptyset$ ...
0
votes
1answer
72 views

For two regular languages, why is the set of words from one that don't have a subsequence in the other also regular?

In general, a string $x$ is a subsequence of $w = w_1\dots w_n$ if there are integers $i_1<\dots< i_k$ such that $x = w_{i_1}\dots w_{i_k}$. The subsequence is proper if $k < n$ and $k > ...
3
votes
3answers
163 views

Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language

I was wondering about its proof. The direct use of pumping lemma here is not a viability. So a certain teacher of mine proved this with the notion that $a^{n}b^{n}$ being a subset of this language ...
0
votes
2answers
75 views

Can languages with infinite strings be recursively enumerable?

I am not 100% sure about the definition of recursively enumarable languages. Yes I know how are they defined: There has to exist a Turing machine that accepts all wrods of the language and halts but ...
0
votes
1answer
67 views

Show that the regular languages are closed against taking “the second half” [duplicate]

Given $L$ is regular, the proof that $\mathrm{HALF}(L)$ is regular is pretty straightforward to me (e.g., #11 in this link): simply making a NFA and meeting in the middle with 2 original DFAs, the ...
2
votes
2answers
32 views

Method for measuring the 'similarity' between FSA grammars?

I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic ...