Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,557
questions
0
votes
0answers
55 views
Finite state transducer that multiplies numbers
How is possible to construct a finite state transducer that multiplies a number by 5? We can assume that numbers are supplied in binary notation, from least significant bits to most significant.
1
vote
1answer
59 views
Write a CFG for the language $\{0^n 1^a 2^b \mid n = a+b\}$
I would like some help for the computation theory.
There is a PDA that accepts the language $\{0^n 1^a 2^b \mid n = a+b\}$, so how can I express it into context free grammar? Any help would be ...
1
vote
1answer
42 views
What is the language of Sigma^n? Confused about meanining
I am learning the Theory of Computation, and I came across the language $\Sigma^n$. Could someone please explain what that could mean if $\Sigma$ is the alphabet?
Thank you so much!
1
vote
1answer
32 views
Finding right quotient of $a^*b^*/b^*.$
I argue that right quotient of $a^*b^*/b^*$ is $a^*$,is that true?any help or argument to accept or reject my argument will be appreciated:)
0
votes
0answers
22 views
What's the union between a decision problem and its complement
I see the union of problems as something like this:
$P=F\cup G$
$P(\omega):$
$\;\;\;\;if\; F(\omega)==True: return \;\; True$
$\;\;\;\;else\;if\; G(\omega)==True: return \;\; True$
$\;\;\;\;else: ...
0
votes
0answers
48 views
How can I show that the function f(u, v) = uv is computable in programming language S_n. Here uv is concatenation of the words u and v
This is in reference to a question I found in chapter 5 (Calculation on strings) Computability, Complexity, and Language by Martin D. Davis
2
votes
1answer
98 views
Minimal DFA accepting strings whose length is divisible by $x$ or $y$
Consider the language of all strings whose length is divisible by either $x$ or $y$, where $x,y \geq 1$.
After trying various values of $x$ and $y$, I noticed made the following observation:
If one ...
0
votes
0answers
535 views
Turing machine that recognizes the language $\{a^{n}b^{2n}c^{3n}|\ n\ge0\}$
I'm pretty sure that the Turing machine state diagram I drew accepts all strings in the language $\{a^{n}b^{2n}c^{3n}|\ n\ge0\}$, but how do you verify this? Likewise, how do you verify that this ...
0
votes
3answers
155 views
Difference between a regular and a non-regular language
Suppose $L_1$ is a regular language and $L_2$ a non-regular one, then:
is $L_1\setminus L_2$ REGULAR/NON REGULAR/BOTH OF THEM?
is $L_2\setminus L_1$ REGULAR/NON REGULAR/BOTH OF THEM?
0
votes
2answers
318 views
Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? How can it be shown?
Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free?
If so, can there be a pushdown automaton described for it?
If not, does the pumping lemma apply?
0
votes
0answers
39 views
What kind of automaton recognizes closed terms of the lambda calculus?
There seems to be an interesting model of computation involved in determining whether a term from some programming language has any free variables. It's a tree traversal that seems almost like the ...
0
votes
1answer
51 views
Can PDA accept only by final state without finish reading input?
I am defining, a string $w$ is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input $w$ (no matter whether the ...
0
votes
1answer
67 views
Myhill-Nerode classes for a Language $L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$
This problem is from an exercise sheet so it would be nice if you could guide me to the solution.
The problem:
For $ k \in \mathbb{N}\setminus\{0\}$ let
$$L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}...
-1
votes
1answer
37 views
Prove that the class of regular languages is closed under the Kleene + operation. That is, show that if L is regular, then so is $L^{+}$
This is my attempt at a proof:
Let $E$ be a $REGEX$ accepting $L$. We claim the $REGEX$ $E^{'} = E^{+}$ accepts L. i.e. $L(E^{+}) = (L(E))^{+}$
$L^{+}$ is regular since there is a $REGEX$ $E^{+}$ ...
0
votes
1answer
44 views
Generate the context free grammar for the following language: $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$
Given the following language, I am tasked with giving a context-free grammar that generates it.
$\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$
Would this be correct?
$A \rightarrow aaaA$
$B\...
0
votes
1answer
75 views
Create a Deterministic Finite Automaton for a regular expression
I want to create a finite state machine that accepts the following language:
$$
L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\}
$$
So I began by writing a regular expression ...
1
vote
2answers
94 views
Proving some subsets of a regular languages to be regular languages
I have to prove that if a language $L$ is regular then:
a) $NONPREFIX(L)=\{u \in L / $none of the prefixes (not $\epsilon$ or $u$) of $u$ are elements of $L \} $ is regular
On this one I think I can ...
2
votes
2answers
61 views
Irregularity of $\{0^x1^y : y \nmid x\}$
The language $L=\{W\in\{0,1\}^{*} \mid W=0^{x}1^{y} \text{ where } x\geq0, y>0 \text{ are integers and } y\nmid x\}$ is not regular.
How would one prove this using Pumping Lemma?
I thought about it ...
1
vote
1answer
1k views
What does it mean for a grammar to be LR(0)?
I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0).
For part of an assignment I had to form the DFA for a grammar, which I had no issues with....
2
votes
1answer
79 views
How can I show that this language is context sensitive?
I have this language $L=\{a^nb^nc^n,n\geq0\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?
2
votes
1answer
86 views
What are the most used statements in programming (ranked)?
I was wondering if there are any resources for a study/ranking of the most frequently used statements (by statements I mean assigning, invoking, instantiating etc, like in C#) in programming overall (...
1
vote
0answers
59 views
How to prove a statement in regular expression?
I cannot figure out how to go about proving this statement in regular expression.
$$ L(R_1) \subseteq L(R_2) \subseteq L(R_3) \implies L(R_1^*+R_3)^* \subseteq L(R_2^*+R_3^*) $$
Here's what I have ...
0
votes
1answer
44 views
Formal proof of language accepted by a specific CFG
Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules:
\begin{align}
&S \to aS \mid B \\
&B \to abBc \mid \epsilon
\end{align}
Please provide a formal proof for the following ...
0
votes
1answer
117 views
Proving the language of non-primes is in NP
I am learning about NP problems and found this problem in my textbook that I was not sure how to answer, and was looking for some help on how to start the question.
Show the following language is in ...
0
votes
0answers
39 views
How did we go from Binary to something like Python?
If there's one thing the pandemic has shown us its that High school Geometry did not save us. I am a high school math teacher and I understand my job and its usefulness only exist in a post scarcity ...
0
votes
1answer
70 views
If two languages are decidable, can one be mapping reducible to the other?
If I have two decidable languages $A$ and $B$, is $A \leq_m B$ true? How would I show this?
0
votes
0answers
54 views
When are existential quantifiers in the intuitionistic propositional calculus eliminable and when not
I am so ignorant I don't even know where should I ask this - on FOM? On mathoverflow? On cstheory? So please consider as sort of a meta-question readdressing me in case you think this is a wrong site. ...
5
votes
4answers
598 views
Is there a formal definition of sub-instances or sub-problems?
A decision problem is denoted as a language $L \subseteq \Sigma^{*}$.
For every instance $x \in \Sigma^{*}$, we say $x$ is a yes-instance if $x \in L$ and a no-instance if $x \not\in L$.
For some ...
0
votes
1answer
48 views
Is this an unambiguous CFG that is not LR(k) for any k?
The grammar is this:
$$S \rightarrow a B c $$
$$B \rightarrow b B b $$
$$B \rightarrow \epsilon $$
The LR(1) states that I worked out were these
$$(1)$$
$$S \rightarrow .aBc$$
$\\\\$
$$(2)$$
$$S \...
0
votes
0answers
37 views
Check if given safety properties are regular, and if so construct NFAs
Let $\mathit{AP} = \{a, b, c\}$. Consider the following LT properties:
Between two neighboring occurrences of $a$, $b$ always holds.
Between two neighboring occurrences of $a$, $b$ occurs more often ...
1
vote
0answers
33 views
Name for a function on formulae that does not break the structure of given formula
I have two logics, $L_1$ and $L_2$, and a mapping $f: Formulas_{L1} \rightarrow Formulas_{L2}$, and want to argue that the mapping is "nice", in the sense that it is structure-preserving. ...
0
votes
0answers
145 views
How would I prove that nondeterministic Turing machines are undecidable?
How would I go about proving that the language:
$$A_{NTM }= \{\langle N, w\rangle | N \text{ is a nondeterministic TM and } N \text{ accepts }w\}$$
is undecidable?
I looked at the proof for $A_{TM}$ ...
1
vote
1answer
62 views
Characterization about Kleene Closure, when is a language $L=L^*$?
I'm trying to find a characterization of when $L=L^*$.
I think I have one, but maybe is trivial, but I don't know if the proof is correct.
Claim: $L=L^* \Leftrightarrow L=LL$.
Proof:
If $L=L^*$ then ...
1
vote
0answers
24 views
Is there a direct way to obtain the RE for the handle-finding DFA of a grammar?
LR parser for a (CFG) grammar uses a handle-find automaton (which is a DFA) to find the handles. Such automata can be constructed by computing the canonical collection of sets of LR(0)/LR(1) items.
Is ...
3
votes
0answers
190 views
is it decidable whether a grammar in Chomsky normal form has useless rules?
Given a context-free grammar in Chomsky normal form, is it decidable whether that grammar has any useless rules? By "useless", I mean a rule that can be omitted from the grammar without ...
0
votes
1answer
33 views
Is this concatenation ({a} · {b})^2 ≠ a^2 · b^2?
I presumed they were equal, such that both resulted in aabb. However, I'm told they are false and I don't know why.
Is it because in the second one, we would ...
4
votes
1answer
385 views
Undecidability of "is this CFG prefix-free?"
I'm having difficulty proving undecidability of "is this CFG prefix-free?". (this proof is given as problem 5.32b in Sipser 3rd edition).
Another thread has the very different question "...
0
votes
1answer
38 views
Are these production rules for a formal grammar?
I have a question on if production rules of a formal grammar are being specified correctly. Wikipedia defines the syntax of grammars as the following finite set of production rules, where it states ...
1
vote
2answers
222 views
How to tell if a grammar is LALR(1) formally?
There is an “informal” definition of $\operatorname{LR}(k)$ (can be recognised by a parser that looks at $k$ symbols ahead) and a “formal” one (as a property of the set of rightmost derivations ...
0
votes
2answers
32 views
string concatenation vs language concatenation
What exactly is the difference between
$$
C = \{a^*\}\{b\}\{a^*\}\{b\}\{a^*\}\{b\}
$$
and
$$
D = \{a^nba^nba^nb | n \geq 0 \}
$$
It is known that D is non-regular and C is regular, but I am not sure ...
0
votes
2answers
241 views
How do Context Sensitive Grammar systems work?
The Quest: Use context sensitive grammar (CSG) to produce an equal N number of repeating a, b, and c using the alphabet {a, b, c}. For example, if N = 5 use CSG and a, b, and c to produce a result ...
0
votes
1answer
149 views
Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$
Does there exist a Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$
I have tried to find a pushdown automata and it turned out to be a ...
1
vote
1answer
106 views
How to find the language of a CFG from Production rules
I'm having problems in finding language of the CFG from given production rules. For example if the production rules are
\begin{align}
&S \to AS \mid \epsilon \\
&A \to aa \mid ab \mid ba \mid ...
6
votes
1answer
384 views
What are the closure properties of LL(k) languages?
Suppose I have two LL languages $L_1, L_2$, both describable by LL($k$) grammars for the same $k$, and regular language $R$. Which of the following are also LL languages, and can they be described by ...
0
votes
0answers
111 views
Generalization of automaton - Sipser example 1.33
I am trying to construct a nfa that generalizes Example 1.33 found in the book Introduction to the Theory of Computation by Sipser, but I am quite sure
that my transition function is wrong. I'd like ...
1
vote
1answer
109 views
Proof that languages are Turing-recognizable iff computably-enumerable
A very small question on this proof, which I found as Theorem 3.21 in Sipser's, and in my lecture notes.
In the "only if" direction, we assume that a Turing machine $M$ recognizes some ...
1
vote
2answers
38 views
Can you say anything interesting about a language knowing only that it is prefix-closed?
Suppose $L$ is an arbitrary formal language over a finite alphabet $A$, and suppose that $L$ is closed under prefixes (i.e. if $w \in L$, and $u$ is any prefix of $w$, then $u \in L$).
Knowing only ...
4
votes
1answer
653 views
Is every unambiguous grammar regular?
While searching for an answer to this question I found out that there is an unambiguous grammar for every regular language.
But is there a regular language for every unambiguous grammar? How can I ...
0
votes
1answer
62 views
Can this language be called regular?
Recently, I was facing some problems in effectively proving the following :
Consider the alphabet Σ ={0,1,2,...,9,#}, and the language of strings of the form x#y#z, where x,y and z are strings of ...
0
votes
0answers
79 views
a^ib^jc^k, i < j < k is a context-sensitive language, how can prove it as a context sensitive
I've been pondering this question for a long time, that $a^ib^jc^k, i < j < k$ is a context-sensitive language, how we can prove it to be context sensitive or
which grammar can generate such a ...
