Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Formal languages are sets of strings, i.e. sequences over symbols from some alphabet.

In general, the field of formal languages studies mathematical and logical properties of and relationships between languages (or sets) of strings (or sequences of symbols) over alphabets (or sets of symbols). Commonly encountered varieties of formal languages are regular languages, context-free languages, context-sensitive languages, recursive languages, and undecidable languages.

Question about formal languages including automata theory, grammars.

Roughly corresponds to arXiv tagcs.FL and ACM Subject Classes F.1.1, and F.4.3.

The tag is better suited for question about computability and Turing machines.

Wikipedia

Related tags:

2954 questions
147
votes
5 answers

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 sometimes the resulting expressions are messy.…
Raphael
  • 73,461
  • 31
  • 185
  • 415
101
votes
5 answers

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. How do I show the opposite, though? My TA has…
Raphael
  • 73,461
  • 31
  • 185
  • 415
100
votes
10 answers

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 given language is regular. How do I show the…
Raphael
  • 73,461
  • 31
  • 185
  • 415
76
votes
1 answer

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 all $k$? So how is the situation really? In…
Raphael
  • 73,461
  • 31
  • 185
  • 415
56
votes
9 answers

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 the following $L'$ is regular, too? $\qquad…
corium
  • 909
  • 1
  • 8
  • 9
54
votes
1 answer

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's the question: Show that the language $L = \{xy…
Dave Clarke
  • 20,375
  • 4
  • 72
  • 114
51
votes
2 answers

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 considering problems? And how do these relate to…
Joey Eremondi
  • 30,486
  • 6
  • 70
  • 124
45
votes
2 answers

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 instance, push-down automata store information in a…
Patrick87
  • 12,994
  • 1
  • 48
  • 78
44
votes
0 answers

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA : It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a regular tree grammar (Chapter 2). Both formalisms hold…
john_leo
  • 1,921
  • 14
  • 26
40
votes
2 answers

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 inherently ambiguous if and only if all context-free…
Patrick87
  • 12,994
  • 1
  • 48
  • 78
36
votes
3 answers

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 string $w$ in $L$ of length at least $p$ ($p$ is called…
Phil Wright
  • 943
  • 1
  • 10
  • 13
35
votes
9 answers

What is the significance of context-sensitive (Type 1) languages?

Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a state machine with no external memory (i.e., a finite automaton), Type 2 by a state machine with a single stack (i.e. a push-down automaton) and Type 0 by a state machine…
bitmask
  • 1,783
  • 2
  • 16
  • 20
33
votes
4 answers

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^{R}$ is also accepted by some finite; $L^{R}$…
Cat
  • 333
  • 1
  • 3
  • 4
33
votes
2 answers

Why is a regular language called 'regular'?

I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata. He defines a regular language as anything that can be described by a finite automata. But I…
Phil Wright
  • 943
  • 1
  • 10
  • 13
30
votes
2 answers

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 a context-free grammar for the language. Are there…
D.W.
  • 170,893
  • 23
  • 241
  • 528
1
2 3
…
99 100