Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,558
questions
-2
votes
0answers
19 views
Is {wєL1| Ǝv wvєL2} regular if L1 & L2 regular languages?
Will the language {wєL1| Ǝv wvєL2} be regular if L1 & L2 regular languages?
-3
votes
0answers
23 views
Formal languages [closed]
first post, hi everyone, got this question in exam,
how many complete Deterministic finite automaton we can get with 2 states, and with n states( considering n big number to get a general formula), Σ =...
0
votes
0answers
16 views
How to prove that this "priority" strategy (in ANTLR4) solves the "dangling-else" ambiguity?
As shown in this post @ stackoverflow, ANTLR4 seems able to resolve the "dangling-else" ambiguity @ wiki in the following "if-then-else" grammar by prioritizing the "...
0
votes
0answers
21 views
Turing Machine that accepts L(M1) = {x^n y^2n z^n | n ∈ N}
I'm trying to design a Turing machine that accepts all strings in the language $$\{x^{n}y^{2n}z^{n}|\ n\in N\}$$ but I'm having trouble getting it to accepts when n> 1, for some reason it rejects ...
0
votes
3answers
203 views
How it's possible decide CNF by having a turing machine that decide SAT?
Suppose we have a Turing machine $M$ as black box that decide $SAT$ problem. Now suppse we have a $CNF$ formula $\phi$ with $n$ variables. How it possible checking satisfiblity of $\phi$ and then ...
0
votes
0answers
19 views
Is there any problems with equating Turing Machines with Algorithms and Language with Problems?
In a lot of the online explanation of complexity theory, the author proposes the following.
"The definition associated with complexity theory (e.g., definition of
NP) is phrased in terms of ...
0
votes
0answers
29 views
How do right contexts work in context-sensitive L-Systems?
I am working on an implementation of context-sensitive 2-L systems as described in The Algorithmic Beauty of Plants by Aristid Lindenmayer, and am in need of clarification regarding context matching ...
0
votes
1answer
39 views
Is the language $L=\{a^nb^m:n,m\in\mathbb{N}\land n-m=5 \}$ regular or not regular?
I'm trying to understand how to prove a language is regular or not regular, for example this language: $$L=\{a^nb^m:n,m\in\mathbb{N}\land n-m=5 \}$$
Is this language regular or not?
My solution
Using ...
0
votes
3answers
64 views
Proof that the complement of a finite language is always an infinite language
Let's say that we have a language $L$ that is finite.
How can I prove that the complement of $L$, i.e., $\bar{L}$, is always an infinite language?
Obs.: infinite language in this case means that is ...
2
votes
1answer
34 views
What does $g \to \lambda$ mean in the L-System for the dragon curve?
I am playing with L-System using the wonderful tool jflap. Below is the L-System for the dragon curve in the "JFLAP book: JFLAP – An Interactive Formal ...
1
vote
1answer
25 views
A turing machine L takes a machine <M> which has to halt at for least n Inputs
I've been wondering about this problem for a while:
Say we have L = { <M>, n | M has to halt for at least n Inputs}
and multitapes are simulating various inputs bla bla
How do I count how many ...
-1
votes
0answers
25 views
Say what language is generated by the context-free grammar
In each case below, say what language (a subset of {a, b}∗) is generated by the context-free grammar with the indicated productions.
S→ aSa | bSb | aAb | bAa
A → aAa | bAb | a | b | Λ
I tried to solve ...
-1
votes
0answers
32 views
$Prove\; that\; L=a^i b^j c^k: i\le j\le k$ i s not context free language
Proof-:
Assume L is CFL.
Let p is pumping constant for L. w exists in L such that |w|$\ge p$
Let w=$a^p b^p c^p$ |w|$\ge$3p so everything is fine.
Now let us see all decompositions of w such that-:
vy$...
0
votes
3answers
227 views
Can the diagonal language be empty?
We defined the diagonal language as follows in the lecture:
\begin{align*}
L_{\text{diag}}=\left\{w \in \left\{0, 1\right\} ^{*}\mid w=w_{i} \text{ for some }i \in \mathbb{N} \text{ and }M_{i} \text{
...
0
votes
2answers
41 views
When you convert epsilon NFA to NFA, how do you decide the final states of resultant NFA?
The question is-:
THIS is the transition table for NFA-:
Final result as shown in youtube video.
https://www.youtube.com/watch?v=GjLiXk0imi0&list=PLENQMW_c1dimRCKF3bjUqHaH8dvJkapSw&index=49
...
0
votes
0answers
33 views
Show that if $A$ and $B$ are recognizable subsets of $\Sigma^*$ then so is $A \cup B$, $A \cap B$ and also $\Sigma^* - A$
I am working through a chapter of a book by Samuel Eilenberg about Automata, Languages and Machines as part of an university course in computer science.
And as an exercise in this chapter I have to ...
0
votes
1answer
23 views
Understanding about pumping lemma for regular language-confusions of beginner-:
I want to understand how is this proof working.
What I know-:
Pumping lemma for regular language-:
Let $L$ be regular language. Then there exists a constant $n$ which depends on $L$ such that for ...
-2
votes
0answers
16 views
How to choose splits in pumping lemma to prove language not regular
I am confused how we choose $0\;^{n-p}$ 1 and $0^n$ What's the logic going on here?
0
votes
2answers
46 views
Can a non-recognisable language have a recognisable subset?
If $L\notin$ RE, can there be a language $L'\subseteq L$ such that $L'\in$ RE? Or is it necessarily true that $L'\notin$ RE for all $L'\subseteq L$.
1
vote
1answer
53 views
If a TM accepts a non-regular language, its space complexity is $\Omega(\log \log n)$
I have been given an assignment that I'm having a very hard time understanding.
The assignment is to prove that if an algorithm accepts a non-regular language, the complexity is $\Omega(\log \log n)$ (...
1
vote
1answer
43 views
How to write a non-ambiguous grammar for the syntax of lambda calculus?
I tried to write a non-ambiguous grammar for lambda calculus, but it does not really work. The recursive-descent parser is easy to write though. I googled but all results I collected so far are ...
1
vote
1answer
33 views
What does ({a,b}*)² mean?
Pretty much just the title. Is it all possible combinations of a and b that have 2 letters ?
0
votes
1answer
19 views
What is the subset of CFGs called where each expansion must be the same?
I was wondering about a kind of grammar where we can expand rules of the form A -> X|Y|... with A being a nonterminal and <...
2
votes
1answer
36 views
Transitions of Turing machine in Cook Levin theorem proof
I am looking at the proof of the Cook-Levin theorem in Computers and Intractability: A Guide to the Theory of NP-Completeness. In particular, I find one thing ...
0
votes
0answers
20 views
Which type of language and machine can parse the following string
Assume that I want to be able to parse strings that follow those rules:
...
1
vote
1answer
40 views
Is language $a^mb^nc^n, m \not= n$ context free
I need to say Is language $a^mb^nc^n, m \not= n$ context free
I managed to find a grammar for $L1 = $ { $a^lb^mc^n | l=m$ or $m = n$ }, but I couldn't find the one I needed. Maybe it is impossible, ...
1
vote
1answer
148 views
A computable language with a non-computable language that is prefix-free
We say that a language $L$ is prefix-free if for every word $s\in L$ there does not exist a nonempty string $w\in\Sigma^*$ such that $sw\in L$ (i.e. no word in the language is a prefix of some other ...
-2
votes
2answers
61 views
Prove that the class of regular languages is closed under three operation
We define an operation three on strings as three(c1c2c3c4c5c6...) = c3c6... then the above-described definition is extended to languages. Prove that the class of regular languages is closed under this ...
1
vote
2answers
42 views
PDA with multiple element access - $i$ - access PDA
We define an $i$ - access PDA as a PDA that can manipulate the top $i$ characters in the stack, where $i>0$.
Given a transition function of the form $\delta(p,x,c,d) \to (q,c')$, where $d \le i, d &...
0
votes
1answer
41 views
Size of minimal DFA
Assume a given NFA for a regular language with $n$ states. It is clear that determinizing it may result in an DFA with $\Omega(2^n)$ states. However, the minimization might decrease the number of ...
-1
votes
1answer
62 views
Show that {xy : x,y ∈ {a,b}*, |x| = |y|, x ≠ y} is a not a regular language
Actually, I know that there are many examples showing how this is a contex-free language, but I can't find any that show it isn't regular. I would appreciate if I could have a solution step by step ...
0
votes
2answers
63 views
Show that $\{xy : x \in \{a\}^*, y \in \{b\}^*, |x| = |y|\}$ is a not a regular language
I have been asked as an exercise how to prove that this is not a regular language. first I tried to use the pumping lemma, but I got stucked. Th erxercise hust said to prove thata this isn't a regular ...
-1
votes
1answer
26 views
complement of concatenate languages equal to complements concatenated?
please help me with this one.
(a formal answer would be much appreciated)
∀L1, L2 ⊆ Σ:
(L1 · L2)^c = L1^c · L2^c
when · represents concatination and ^c the complement language.
do not know if ...
0
votes
1answer
23 views
Variant of Chomsky Normal Form for Languages with Strings of Length $\ge 2$
Given a context-free grammar $G$ for a language $L$, where $L$
contains strings of length greater than 2, show that there exists some
context-free grammar $G'$ which generates $L$ such that every rule ...
2
votes
2answers
57 views
If L is regular so is the language of compressed doubles
Suppose L is a regular language over the alphabet $\Sigma$. I need to prove that
$$ L'=\{x_0\cdots x_n:x_0x_0x_1x_1\cdots x_nx_n\in L, \ \ x_i\in \Sigma\}$$
I thought I could take a DFA which computes ...
0
votes
1answer
40 views
Difference between Counter-machine and stack machine
I read from this question that counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol).
My question is counter machine means counter coexist ...
1
vote
1answer
44 views
Could I apply Rice theorem for both TM's property and language property?
I read that Rice theorem applicable only for language property not for machine property. But today I have read from stack exchange and one site they are applying Rice theorem on machine also. My ...
0
votes
1answer
46 views
Is set of all RE languages $\subseteq\\$ $\Sigma^{*}?$ [closed]
We know that any languages $\subseteq\\\\$ $\Sigma^{*}.$ Because any language collection of string over alphabet. And we know that set of all languages is $2^{\Sigma^{*}}$ which doesn't $\subsetneq\\\\...
1
vote
1answer
17 views
The Turing Machine in the proof of Time Hierarchy Theorem
In the proof of the Time Hierarchy Theorem, Arora and Barak writes:
Consider the following Turing Machine $D$: “On input $x$, run for $|x|^{1.4}$ steps the Universal TM $U$ of Theorem 1.6 to simulate ...
2
votes
1answer
30 views
How can I represent this description in set builder notation?
The language that accepts strings with the number of 0s being congruent with 1%3 and an even number of 1s over the alphabet {0, 1}.
0
votes
1answer
54 views
For Turing machines, if the input variables increase, will the state set Q increase ? will the tape alphabet Γ increase?
For Turing machines, if the input variables increase, will the state set Q increase ? will the tape alphabet Γ increase?
For example, for the SAT problem, the first question is whether the Boolean ...
3
votes
2answers
3k views
Do Turing machines have memory registers?
I am working on chapter one of the textbook Computational Complexity: a modern approach by Arora, S., & Barak, B. They begin by defining a turing machine (TM) and then prove equivalence between ...
2
votes
1answer
52 views
How to determine the finite or infinite number of words in a formal language
Let be:
Uppercase letters — non-terminal symbols.
Lowercase letters — terminal symbols.
Possible cases:
The number of words is 0 (infinite substitutions). Examples: $$\{S \rightarrow aS\}, \\ \{S \...
3
votes
0answers
57 views
Some guess about concatenation of intersection of languages
I know this is an amateur question but is it true to say that for any three nonempty languages $L_{1},L_{2},L_{3}$ over an alphabet $\Sigma$ we have $L_{1}(L_{2} \cap L_{3}) = L_{1}L_{2} \cap L_{1}L_{...
1
vote
1answer
32 views
Prove or disprove: $L^n=M^n\nRightarrow L=M$ where $L$ and $M$ are languages
In a homework assignment, it's asked
For any alphabet $\Sigma$; for all languages $L$, $M$ on $\Sigma$
Prove that $\forall n>1$, $L^n=M^n\nRightarrow L=M$
The student and I tried in vain to make ...
3
votes
1answer
64 views
Can you diagonalize a language out of CSL?
In recursion theory, it is possible to diagonalize a computable function out of the class of primitive recursive functions. Can you do the same with context-sensitive languages? I was thinking we ...
1
vote
1answer
30 views
Test whether words of less a's than b's or c's but not at the same time is context-free
I want to test whether $L= \{w\in\{a,b,c\}^* \mid |w|_a<|w|_b \text{ or } |w|_a<|w|_c,\text{ but not at the same time} \}$ is CFL or not (I assume not), but I am struggling to do so.
The closest ...
1
vote
1answer
69 views
Are programs just "words" of a formal language?
Every formal language is a subset of E*.
Let's say this formal language is python. If a program is syntactically correct, then the Python Automata accepts the "word", which is the program. ...
1
vote
1answer
44 views
Given two languages $A,B \subseteq \Sigma^*$, prove that $A/B$ is semi-decidable if both the languages are semi-decidable
I have found two interesting questions regarding the quotient of languages, described as:
$A/B=\{w \mid \exists z\in B\land wz\in A\}$
The first one is:
Let $A$ and $B$ be regular languages, prove ...
2
votes
1answer
111 views