Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [formal-languages]

Formal languages are studied in computer science and linguistics. They are usually defined using various types of grammars (e.g. regular, context-free) and automata (e.g. deterministic and pushdown automata, Turing machines). There is a hierarchy of formal languages, which is based on the type of grammars and automata which can be used to generate them.

Formal languages are studied in computer science and linguistics. They are usually defined using various types of grammars (e.g. regular, context-free) and automata (e.g. deterministic and pushdown automata, Turing machines). There is a hierarchy of formal languages, which is based on the type of grammars and automata which can be used to generated them.

1984 questions
12
votes
3 answers

What is the difference between language of empty string and empty set language?

I am reading Introduction to Automata theory by Ullman. It says the empty set and set containing empty string is different. I am unable to understand the difference between them as the empty string doesn't have any character. Forgive me if this is…
SphericalCow
  • 265
7
votes
1 answer

finding right quotient of languages

Can someone enumerate in detail, the steps to find right quotient of languages, i.e. $L_1/L_2$. Using an example will be great.
maximus
  • 71
6
votes
2 answers

Is the inclusion of a regular language in a context-free language decidable?

Is the following problem decidable in general: Given a regular language $R$ and context-free $C$, is every string in $R$ also in $C$? That is, is $L(R)\subseteq L(C)$? What about $L(C)\subseteq L(R)$? I know that this is decidable if $R$ and…
Dave Clarke
  • 188
5
votes
2 answers

How can a formal language $L$ concatenated with itself $L^k$ ever equal $L^{k+1}$

I’m seeking an explanation of how any formal language L concatenated with itself $k$ times, $L^k$, can equal that same language concatenated with itself $k+1$ times, $L^{k+1}$. The problem I’m working on specifically asks for me to provide some…
Adrian
  • 53
  • 4
5
votes
3 answers

Every infinite regular language has a non-regular subset?

I found some examples of infinite regular languages having non-regular subsets. Is it true in general?
user55531
  • 309
4
votes
1 answer

I don't understand P-Q system in GEB

Up front some apologies since I am not a mathematician and English is not my native language so it might be that I am missing some basics here. If so please don't flame me but just point me to some place where I might read up on basics first. I am…
Dalibor Čarapić
  • 193
4
votes
1 answer

Is this language semidecidable?

I recently started self studying about algorithms and decision problem, so I don't have a firm grasp on this particular area. In this context I found myself thinking about the following . If $L_1$ is semidecidable and $L_2$ is decidable, what can…
rodney
  • 41
4
votes
0 answers

Unique factorization in human language? (Kummer rings at stake?)

I keep on bringing some interesting analogies (at least I hope they are) between the study of language by authors such as Zellig Harris or Noam Chomsky and some mathematical issues I have read a bit about as a layman in maths. I quote some…
Javier Arias
  • 2,033
4
votes
2 answers

Mathematical structures of language (Zellig Harris)

I would like to get some feedback from you regarding the mathematical structures which describe the objects and/or properties described in the paragraph below, which I take from the book Mathematical Structures in Language by Zellig Harris, from…
Javier Arias
  • 2,033
3
votes
1 answer

How to prove a language is decidable

I would like to see some proofs to show if a particular string in machine $M$ which DFA is decidable or not. I am trying to find some results on this but those are not appropriate. Any examples or proofs would be of great help. The scenario I am…
Deepak
  • 57
3
votes
2 answers

Is my proof of 2 languages equality correct?

I started to self-study the formal languages theory, and tried to solve the following problem: Problem Prove, that these 2 languages are equivalent: $$ \Sigma = \{a,b,c\}\\ L_1 = \{(abc)^na | n \ge 2\},\\ L_2 = \{ab(cab)^nca|n \ge…
user4035
  • 351
3
votes
2 answers

String sets commutative under concatenation

If $A$ and $B$ are languages over the same alphabet $\Sigma$, what can we say about $A$ and $B$ if $AB = BA$? Is there some way to characterize all languages with this property?
Hemispherr
  • 851
3
votes
1 answer

Name of a theorem about the existence and uniqueness of a solution of a language equation

I'm looking for the name of this theorem: Let $P$, $Q$ be languages. Let $X$ be a language variable. Then the language equation $X=PX + Q$ (here $+$ denotes union) has a solution $X=P^*Q$, and the solution is unique if the null string doesn't…
user12331
  • 299
3
votes
1 answer

Formal language homework problem - extend(L)

This is my attempt to solve an exercise from a formal languagues class. Consider the following definition: extend(L) = { w $\in$ $\Sigma^*$ | $\exists$ x $\in$ L, y$\in$ $\Sigma^*$ . w = xy } In words: extend(L) is the set of all strings with…
marcos
  • 341
3
votes
2 answers

Determine if a Turing Machine M, on input w, will move its head to the left, at least once

Here is a problem from my formal languages class Consider the following problem: Determine if a Turing Machine M, on input w, will move its head to the left, at least once. Is this problem decidable? Can Rice's theorem be applied on…
marcos
  • 341
1
2 3
…
10 11