Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,066
questions
0
votes
1answer
12 views
Are models of computation closed under composition?
It's common to ask whether a particular class of languages $\mathcal{C} \subseteq \mathcal{P}(\Sigma^*)$, for some alphabet $\Sigma$, is closed under complement, or union, or intersection, or ...
0
votes
0answers
22 views
If $L$ is a regular language then so is $L/a =\{w | wa ∈ L\}$, where $L$ is a language over $\Sigma$ and $a \in \Sigma$
I'm trying to work out a proof by construction that $L/a$ would be regular.
$a$ is any final symbol at the end of an accepted string, so I figured the only part of the machine that would have to be ...
0
votes
2answers
72 views
Let L be any non-empty language over an alphabet Σ. Show that $L^2$ ⊆ $L^3$ if and only if λ ∈ L
I have this question in my Theoretical Computer Science class on the topic of Automata and Formal Languages.
$$ λ ∈ L \iff L^2 ⊆ L^3$$
I thought of showing it by proving the contrapositive but I was ...
-2
votes
0answers
17 views
decidability-countability-grammers-languages [on hold]
L=a language
M= a TM
Lc= complement of L
1) L={ | M is a TM, encoded with some alphabet } ;
L is recursive
2) L=set of all cfls generated by some cfg;
...
0
votes
1answer
46 views
Decidability of the language of all deterministic LBA where all states are reachable
I have a exam task with 3 parts. (b) is no problem. I got a solution for (a) but the way (c) is asked makes me wonder if I even understood (a)
(a) L := { < A > | A is a DFSA, where all states are ...
-1
votes
1answer
49 views
Why is it not possible to prove that two Turing Machines calculate the same function?
I was wondering why it is not possible. Is it because the corresponding language is not decidable, or because of the fact that it is not guaranteed that a Turing machine halts on every input?
0
votes
0answers
16 views
Is there a universal Turing machine for non-deterministic Turing machines? [on hold]
I'm studying Formal Languages and Automata Theory and I found this question. I'm not sure of knowing the answer, so I'm asking for your help.
I know that a universal Turing machine can emulate any ...
2
votes
1answer
37 views
Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve. (With context-sensitive/noncontracting grammar)
I am studying for an upcoming exam and this is an old exam question from two years ago (all exams were made available through our lecturer):
Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}...
4
votes
1answer
32 views
Language containing all unambiguous grammars
Suppose $L$ is the language of the unambiguous grammars. That is, a sentence $w\in{}L$ if it is a string that describes an unambiguous context-free grammar.
Considering that deciding whether a ...
1
vote
1answer
35 views
Prove that a language is bounded if and only if it's finite
Let's assume $L$ is a language. $L$ is bounded if for some natural number $n \in \mathbb N$ applies $|x| ≤ n$, where $|x|$ is a length of a string, with every $x \in L$. Let's also assume that $L$ ...
0
votes
0answers
47 views
Whether following language is linear or not?
I have a language $L= \{a^nb^nc^m : n, m \ge 0\}$.
Now, I wanted to determine whether this language is linear or not.
So, I came up with this grammar:
$S \rightarrow A\thinspace|\thinspace Sc$
$A \...
2
votes
1answer
41 views
Prove: If finite automata M with k states accepts a string with at least k characters, then the language L(M) is infinite
I need to prove that if finite automata $M$ with $k$ states accepts a string with at least $k$ characters, then the language $L(M)$ is infinite. I have no idea where to start. Any suggestions?
2
votes
1answer
28 views
Can't find a mistake in reduction from RE language to a non-RE language
In the book Introduction to Automata Theory there is a question 9.3.4 that asks if a question "whether a language L(M) is infinite" is RE or non-RE? I've seen the answer, that its non-RE, however I ...
0
votes
0answers
15 views
What classifier can recognize differences in two text strings immediately?
I'm playing around with the TextBlob library for python. It has in it a NaiveBayesClassifier as well as a ...
1
vote
1answer
30 views
How to propose a method to construct an automaton?
Given $0 \leq m < k$ and $p \geq 2$ it's defined $$A_{k,m,p} = \{ \alpha \in \{0,1,\dots,p-1\}^* | \alpha \text{ is a p-ary representation of } x \backepsilon x \text{ mod } k = m \}$$
It is ...
0
votes
0answers
29 views
Why do we use CYK algorithm?
Why do we use the CYK algorithm? In my book is written that with CYK algorithm you can faster see if a word is generated by a given Grammer. However I dont get it, because I need like 5 min in order ...
-1
votes
0answers
32 views
DPDA for $\{a^mb^nc^n \mid n,m \ge 1\}$?
How do I create a DPDA for $\{a^mb^nc^n \mid n,m \ge 1\}$?
I have found a solution for the similar language $\{a^nb^nc^m \mid n,m \ge 1\}$ but I am not sure, if the same reasoning applies to the DPDA ...
1
vote
1answer
33 views
Equivalence of different automata
I have a question about the equivalence of different automata. I looked up the similiar questions but sadly none of them are exactly, what I need or am looking for.
I know some of these are ...
-1
votes
0answers
68 views
There are languages I would define as “fermionic”, see below. What is the usual name for their theory?
What is the usual name of the theory I dubbed "fermionic languages", for want of a better term? Let me first explain the naming, from 2 examples.
First, a trivial example from epistemology-fiction, ...
0
votes
0answers
47 views
How to prove this language is not regular?
I am currently learning Pumping Lemma and found this question. But I am not able to prove it not regular. L = { $0^n$ | n is power of 2}. So, here I considered w = $0^{2^n}$ where n is constant of ...
0
votes
2answers
44 views
What makes a common programming language non-context-sensitive but RE?
I have a vague understanding that a (sane) programming language is RE as they are Turing-complete, being able to describe any Turing machine.
But I cannot pinpoint what aspect makes a programming ...
0
votes
1answer
30 views
Pushdown Automaton to accept all strings such that no prefix has more 1’s than 0’s
Design a Pushdown Automata, accepting either by final state or by
empty stack to accept the set of all strings of 0’s and 1’s such that
no prefix has more 1’s than 0’s
This is a homework question,...
0
votes
0answers
29 views
Conditions for string substitution commutativity
Let's say I have two substitutions given [a:=b] and [c:=d]. What are some conditions that hold for a,b,c,d ∈Σ* iff forall s∈Σ* s[a:=b][c:=d]=s[c:=d][a:=b]
Also you can assume that a,c≠𝜀 but you ...
0
votes
1answer
23 views
Need help understanding regular expressions
I was reading up about formal languages (see here: https://pdfs.semanticscholar.org/18b2/d685d5e244a6bfc5a31d312f1e8d322c16a9.pdf) and got confused when I started reading about this expression: 0(0+1)∗...
1
vote
1answer
41 views
What is an example of a Turing-recognizable infinite word, which is not Turing-decidable?
I am confused about Turing Machines that are able to decide languages that contain infinite words.
Are languages with an infinite amount of only finite strings always decidable?
How can a Turing ...
0
votes
1answer
24 views
Condition in Arden's rule
According to Arden's rule, the language equation $X= AX\cup B$, with unknown $X$, has the solution $X=A^*B$, provided $A$ does not contain the empty string.
My question: what is the problem with the ...
1
vote
2answers
34 views
Complement of languages and coNP
By definition, any language (decision problem) $L$ is defined as a subset of $\{0,1\}^*$, where $\{0,1\}$ is the alphabet.
$L^c$ is said to be the complement of the language, and it seems to be ...
1
vote
0answers
46 views
Is there a metric or distance of two languages?
Given a language $L$, I am finding a method to evaluate the advantage of an automaton to decide $L$.
My goal is to decide a language $L$ (and maybe it is not decidable for automata). If one ...
1
vote
1answer
65 views
Determining equivalence classes of $\{w \in \{0,1\}^*\mid$ the $k$-bit of $w$ from the right is 1$\}$
I want to formally write the equivalence classes of the following language:
$$L_k = \{w \in \{0,1\}^*\mid\text{ the } k\text{-th bit of }w\text{ from the right is } 1\}$$
I understand the definition ...
3
votes
1answer
138 views
Can an alphabet for a Turing machine contain subsets of other alphabets?
For example;
Is {0,1,{a,b,c},d,e} a valid alphabet to form a language over and is it usable in any context?
2
votes
0answers
38 views
Pumping lemma for L = {a^i b^j c^k: i < j < k}
I had a question regarding a specific proof I found online that I had some concerns with, I have quoted it below.
Show that the language L = {a^i b^j c^k: i < j < k} is not a context-free
...
2
votes
2answers
102 views
Proof: There exists an irregular language L such that LLLL is regular
As title.
I consider finding a specific L to fulfill the condition stated to prove the statement, however, I have no luck in finding one.
A senior gave me a hint that Lagrange's four square theorem ...
1
vote
1answer
32 views
Pumping lemma regarding {a^2k w | w ∈ {a, b}*, |w| = k}
I had a question regarding the Pumping lemma for regular languages, I have been studying for an exam and came across the question {a^2k w | w ∈ {a, b}*, |w| = k}. In the website it lists the answer ...
-1
votes
1answer
15 views
Is finite subset of a set which contains all non regular languages a regular set?
Let A be a set which contains all non-regular languages. Then set B which is finite subset of A. Then will it be regular ?
I know that A is not recursive enumerable set (undecidable). So I wonder ...
2
votes
1answer
46 views
Context Free Grammar $L=\{a^ib^{2i}c^{2i} | i>1\}$
In one of my exams I needed to find a CFG for $L=\{a^ib^{2i}c^{2i} | i>1\}$.
however, it really seemed to me that it is not a CFG.
I tried to show it is not using the pumping lemma, and think I ...
2
votes
1answer
42 views
How can the union of two 'context-free but not regular' languages be regular?
I cannot understand how the union of two languages which are context-free but not regular, can result in a regular language:
If $L_1$ and $L_2$ are 'context-free but not regular' languages, defined ...
1
vote
1answer
39 views
Substructural Prolog?
Substructural logic is logic without some or all of the structural rules. Is substructural Prolog, substructural logic programming possible? My question is connected with article https://link.springer....
0
votes
1answer
19 views
Given a certain context sensitive grammar, can one find out if a simpler context free grammar exists?
Given a generating grammar, is it possible to reduce it to a context free form, if one exists. One method might seem to be if the context sensitive rules can be reached from higher generating points, ...
0
votes
0answers
25 views
Is this language Deterministic?
I came across this question in Peter-Linz today,
Is the language L= { a^nb^n : n>=1 } U {b} deterministic ?
My doubt is that say we have a case like this {a^5 b^6} U {b}, after popping 5 a's from the ...
1
vote
1answer
52 views
How to characterize equivalence classes induced by Myhill-Nerode theorem?
Given $L=\lbrace w\in \lbrace 0,1 \rbrace^\ast : N_0(w)=N_1(w) \rbrace$, where $N_0(\cdot)$ and $N_1(\cdot)$ mean the number of zeroes and ones respectively, I need to characterize the classes ...
2
votes
1answer
66 views
Are Context Sensitive Grammar with Polynomial Complexity Time?
Accordingly, to the question Chomsky Hierarchy and P vs NP, Context-Sensitive Grammars are on Linear Space.
Assuming a Deterministic Parser is the one which can parse unambiguous grammars in ...
1
vote
1answer
71 views
Can CYK Parsing algorithm generate the parsing tree in O(n^3)?
I found this question What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity? saying CYK Parsing algorithm can compute any Context Free ...
1
vote
1answer
29 views
Is the difference of two context-free languages still context-free?
i am asking myself the following question:
Assuming: A and B are context-free languages, then A - B (difference) must also be context-free language, right?
but I do not know how to prove it.
1
vote
2answers
42 views
L(M)=L where M is a TM that can move right or stay, so L is decidable
Suppose that L(M)=L where M is a one tape TM that can move right or stay.
I need to Show that L is decidable.
I thought of reducing a PDA to this TM, since moving to the right is equivalent to ...
2
votes
1answer
54 views
Turing Machines proof notations
In context of "Computability", I have went over some proofs for Recursion
Theorem using Turing Machine description. A TM $M$ stands for a single tape
Turing machine and $\langle M \rangle$ is the ...
0
votes
0answers
20 views
Is $LR(k) \subset SLR(k+1)$ for $k=1,2,…$? [duplicate]
I know that:
Point 1: Set of languages accepted by $LR(0)$ parsers $\subset$ Set of languages accepted by $SLR(1)$ parsers
Does this logic hold for higher $k$'s? That is, does following fact hold?...
0
votes
0answers
30 views
Does SLR(0), LALR(0) exists?
I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these ...
0
votes
0answers
19 views
Proving correctness of LR parser facts
I have came across following facts while reading some compilers related text. However I did not find them in any standard reference book (mainly dragon book). Are they correct? If yes, how can we ...
0
votes
1answer
62 views
$L = \{ a^{j!} \mid j \geq1\}$ is not context free by pumping lemma
How I use the pumping lemma to prove that the language $L = \{ a^{j!} \mid j \geq1\}$ is not context-free?
0
votes
1answer
28 views
How making non LL, non LR grammar a valid LL grammar, also makes it a valid LR grammar? Is there any connection between LL and LR conflicts?
I might unncecessarily overthinking here, but I had this weird possibly meaning less doubt:
When grammar is neither LL nor LR, it means, both LL and LR parsing tables involve conflicts. LL parsing ...
