Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
409
questions
85
votes
10answers
147k views
How to prove that a language is not regular?
We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...
94
votes
5answers
82k views
How to prove that a language is not context-free?
We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free....
51
votes
8answers
97k views
How to prove a language is regular?
There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular?
For instance, if I am given that $L$ is regular,
how can I prove that ...
26
votes
2answers
36k views
How to prove that a language is context-free?
There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free?
What techniques are there to prove this? Obviously, one way is to exhibit ...
132
votes
4answers
187k views
How to convert finite automata to regular expressions?
Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
23
votes
1answer
7k views
How to show that L = L(G)?
Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is ...
44
votes
1answer
8k views
What is the difference between an algorithm, a language and a problem?
It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
48
votes
1answer
18k views
Show that { xy ∣ |x| = |y|, x ≠ y } is context-free
I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question?
Anyway, here'...
5
votes
2answers
11k views
How do I find a regular expression for a particular language?
I have a language, and I want to find a regular expression for the language. How do I do that? Is there a step-by-step, systematic procedure for that? Pretend I am just learning this topic; what ...
70
votes
1answer
13k views
Language theoretic comparison of LL and LR grammars
People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over ...
20
votes
1answer
5k views
Languages that satisfy the pumping lemma but aren't regular?
Given a regular language $L$, then it is easy to prove that there is a constant $N$ such that is $\sigma \in L$, with $\lvert \sigma \rvert \ge N$ there exist strings $\alpha$, $\beta$ and $\gamma$ ...
44
votes
2answers
1k views
Determining capabilities of a min-heap (or other exotic) state machines
See the end of this post for some clarification on the definition(s) of min-heap automata.
One can imagine using a variety of data structures for storing information for use by state machines. For ...
15
votes
3answers
2k views
What are the possible sets of word lengths in a regular language?
Given a language $L$, define the length set of $L$ as the set of lengths of words in $L$:
$$\mathrm{LS}(L) = \{|u| \mid u \in L \}$$
Which sets of integers can be the length set of a regular language?...
asked Mar 9 '12 at 16:46
Gilles 'SO- stop being evil'
40.6k7 gold badges108 silver badges171 bronze badges
7
votes
2answers
18k views
Context Free Grammar for {a^ib^j | i,j ≥ 0; i ≠ 2j}
Can someone help with this:
$L=\{a^ib^j \mid i,j \ge 0 \text{ and } i \ne 2j\}$
I'm trying to write a grammar for this language?
I don't know how to do this.
I tried this:
$S \rightarrow aaAb \...
6
votes
2answers
7k views
Converting to CFG from a CFL? [duplicate]
I am trying to learn CFG. Now to make a CFG from a CFL it is really difficult for me.
Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem ...
13
votes
2answers
1k views
Closure against right quotient with a fixed language
I'd really love your help with the following:
For any fixed $L_2$ I need to decide whether there is closure under the following operators:
$A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\}$
$A_l(L)=\{...
25
votes
2answers
1k views
Which languages do Perl-compatible regular expressions recognize?
As the title says, I spent a couple of hours last weekend trying to wrap up my mind about the class of languages matched by Perl-compatible regular expressions, excluding any matching operator that ...
8
votes
1answer
8k views
Prove that regular languages are closed under the cycle operator
I've got in a few days an exam and have problems to solve this task.
Let $L$ be a regular language over the alphabet $\Sigma$. We have the operation
$\operatorname{cycle}(L) = \{ xy \mid x,y\in \...
16
votes
3answers
7k views
Example of a non-context free language that nonetheless CAN be pumped?
So basically L satisfies the conditions of the pumping lemma for CFL's but is not a CFL (that is possible according to the definition of the lemma).
13
votes
1answer
7k views
Single-tape Turing Machines with write-protected input recognize only Regular Languages
Here is the problem:
Prove that single-tape Turing Machines that cannot write on the portion of the tape containing the input string recognize only regular languages.
My idea is to prove that this ...
25
votes
3answers
11k views
Pumping lemma for simple finite regular languages
Wikipedia has the following definition of the pumping lemma for regular langauges...
Let $L$ be a regular language. Then there exists an integer $p$ ≥ 1
depending only on $L$ such that every ...
12
votes
7answers
1k views
Is $A$ regular if $A^{2}$ is regular?
If $A^2$ is regular, does it follow that $A$ is regular?
My attempt on a proof:
Yes, for contradiction assume that $A$ is not regular. Then $A^2 = A \cdot A$.
Since concatenation of two non-regular ...
9
votes
1answer
462 views
How can ws with |w| = |s| and w ≠ s be context-free while w#s is not?
Why does (if so) the seperator $\#$ is making a difference between the two languages ?
Let say:
$L=\{ws : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \}$
$L_{\#}=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, ...
10
votes
3answers
3k views
If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?
I'm am stuck solving the next exercise:
Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is context-...
10
votes
5answers
1k views
Language of the values of an affine function
Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let $a$ and $b$ be integers, with $a > 0$. Consider the language of the decimal expansions ...
asked Mar 22 '12 at 1:54
Gilles 'SO- stop being evil'
40.6k7 gold badges108 silver badges171 bronze badges
5
votes
3answers
4k views
Is {wxw^r} a regular language?
Is $\{ WxW^{\mathrm{R}} \mid W,x\in\{0,1\}^+\}$ a regular language? If so, why?
The notation $W^{\mathrm{R}}$ means the reverse string of $W$?
If we consider the best answer in this solution, ...
17
votes
1answer
10k views
Construct a PDA for the complement of $a^nb^nc^n$
I am wondering if this is even possible, since $\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}$. Therefore a PDA that can distinguish a word $w\in\{a^n b^n c^n \mid n \geq 0\}$ from the rest of $...
5
votes
2answers
2k views
Pumping lemma: if you can keep pumping, what does this tell you?
Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this situation,...
3
votes
2answers
6k views
Find a pushdown automaton for { x#y ∣ x ≠ y }
I was told to built a PDA that recognizes the following language:
$$L = \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$$
My attempt is basically to push $x$ to the stack for every $1$ and $0$ ...
24
votes
4answers
80k views
How to show that a “reversed” regular language is regular
I'm stuck on the following question:
"Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then $L^{...
18
votes
3answers
9k views
Is there any uncountable Turing decidable language?
There are many(and I mean many) countable languages which are Turing-decidable. Can any uncountable language be Turing decidable?
9
votes
1answer
5k views
If $L$ is a regular language then so is $\sqrt{L}=\{w:ww\in L\}$
I am interested in proving that $\sqrt{L}=\{w:ww\in L\}$ is regular if $L$ is regular but I don't seem to be getting anywhere. If possible I was hoping for a hint to get me going in the right ...
39
votes
2answers
6k views
Are there inherently ambiguous and deterministic context-free languages?
Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise.
Let us call a context-free language ...
12
votes
3answers
6k views
Easy proof for context-free languages being closed under cyclic shift
The cyclic shift (also called rotation or conjugation) of a language $L$ is defined as $\{ yx \mid xy \in L \}$. According to wikipedia (and here) the context-free languages are closed under this ...
9
votes
3answers
756 views
Context-sensitive grammar for the language of words concatenated with themselves
I'm looking for a context-sensitive grammar that describes the following language:
$L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\}$ .
I've got problems with the fact that no rules such as $X \to \...
8
votes
3answers
5k views
Proving that any CF language over a 1 letter alphabet is regular
I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far:
Let $L$ be ...
4
votes
3answers
3k views
Show that regular languages are closed under Mix operations
Let $L_1, L_2$, two regular languages and the operations:
$$Mix_1(L_1, L_2) =\{ a_1b_1a_2b_2\ldots a_nb_n | n\ge 0 \land a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n\in\Sigma\\ \land a_1a_2\ldots a_n\in ...
2
votes
1answer
2k views
are regular languages closed under division
I am trying to solve this question which appeared in previous exam paper
Can someone help me what i am failing to understand
For languages $A$ and $B$ define $A \div B = \{x \in \Sigma^{\ast} : xy ...
2
votes
1answer
2k views
Context Free Grammar for language L
Can someone help with this:
$L=\{a^ib^j \mid i,j \ge 1 \text{ and } i \ne j \text{ and } i<2j\}$
I'm trying to write a grammar for this language?
I tried this:
$S \to S_1 \mid S_2 \\
S_1 \to aXb ...
2
votes
1answer
1k views
What is one method used to prove each palindrome is in its own Myhill-Nerode equivalence class?
I understand how you can use a contradiction in regard to a DPDA to show a language has finitely many Myhill-Nerode equivalence classes, but what is the method used to show each string of a language ...
20
votes
2answers
21k views
Is the complement of { ww | … } context-free?
Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not?
I'...
26
votes
6answers
7k 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 ...
16
votes
2answers
4k views
Are regular expressions $LR(k)$?
If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
15
votes
2answers
2k views
Number of words of a given length in a regular language
Is there an algebraic characterization of the number of words of a given length in a regular language?
Wikipedia states a result somewhat imprecisely:
For any regular language $L$ there exist ...
asked Apr 4 '12 at 20:13
Gilles 'SO- stop being evil'
40.6k7 gold badges108 silver badges171 bronze badges
11
votes
1answer
1k views
Algorithm to test whether a language is regular
Is there an algorithm/systematic procedure to test whether a language is regular?
In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n : n \in \mathbb{N}\...
10
votes
5answers
2k views
Is there a known method for constructing a grammar given a finite set of finite strings?
From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around?
If given n strings of m length, it should be possible ...
12
votes
2answers
3k views
If $L$ is a subset of $\{0\}^*$, then how can we show that $L^*$ is regular?
Say, $L \subseteq \{0\}^*$. Then how can we prove that $L^*$ is regular?
If $L$ is regular, then of course $L^*$ is also regular. If $L$ is finite, then it is regular and again $L^*$ is regular.
Also ...
6
votes
1answer
5k views
DFA for a strings whose every subsequence of length five has at least two zeroes
I have a regular language consisting of such {0,1}^k sequences, in which every subsequence of length 5 has at least two 0's in ...
3
votes
1answer
2k views
Is regularity of the language accepted by a given Turing machine a semi-decidable property?
Given is the definition of a general problem: $\{ \langle M, S\rangle \mid M \text{ is a } TM, L_M \in S\}$. In words: Given a TM M, does M decide a language that is an element of the given set of ...
10
votes
1answer
342 views
Expressiveness of modern regular expressions
I recently discussed with a friend about a website that proposed regex challenges, mainly matching a group a of words with a special property. He was looking for a regex that matches strings like <...
