Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
1
vote
0answers
21 views
How to give a context-sensitive grammar for words like $a^nba^nba^nb$?
i am struggling on this problem since days: $L = \{a^nba^nba^nb \mid n \in \Bbb N\}$ i have to give for this language a context-sensitive grammar.
2
votes
0answers
8 views
Are the languages recognized by one-counter machines equivalent to deterministic context free language?
When learning automata theory, I notice that John Hopcroft mentioned[1]
In fact, a PDA In fact the languages of one counter machines are accepted by deterministic PDA's although the proof is ...
0
votes
1answer
13 views
Prove that the language L = {w1, w1w2, w1w2w3, ..} is regular, provided wi is in a regular language
Let's assume that we're working over a finite alphabet $\Sigma=\{a, b\}$. How can one prove that $$L_2=\{w_1w_2...w_m| m ∈ \mathbb{N}, ∀i(w_i ∈ L)\}$$ is a regular language, provided that L is regular?...
1
vote
1answer
20 views
A deterministic FA for $0^*1^*$ is required
A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required.
Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$,
both are ...
-1
votes
0answers
39 views
What are the motivations for using a domain-specific language in particular within the database field? [on hold]
Domain-specific languages (DSLs) are common, but what are their advantages? I guess one obvious one is "expressivity" but what about optimization? If so, how? Are there any other advantages?
I am ...
0
votes
1answer
37 views
What are the benefits of languages that are not Turing complete?
Unfortunately I did a degree in CS without much theoretical computer science. One thing I used to hear is that sub languages, or languages which are not Turing complete, allow for better optimization?
...
0
votes
1answer
23 views
Is there a LL(K) Grammar which is not LALR(K) Grammar?
It is easy to know that there are LALR(K) grammars which are not LL(K) because any grammar with left recursion which is LALR(K), is not LL(K) because all LL(K) grammar must be left recursion free. And ...
2
votes
1answer
20 views
When and what must be present on the left-hand side of the turnstile in metalogics?
Let me show the problem on an example...
An actual task from one of the former exams:
Consider a simple functional language:
$$e::= x|n|e_1e_2|\lambda x.e$$
With typing rules:
$$\...
1
vote
0answers
16 views
What's the difference between Acfg and ALLcfg
In computational theory, and talking about CFGs, Turing Machines, and so forth I haven't a satisfactory explanation or definition for what ATM means versus ALLTM or the same or similar uses with ...
1
vote
1answer
28 views
Unambiguousness and determinism of CFGs for them to be LR
I came across this statement:
Note that there are unambiguous grammars for which every LR parser construction method will produce a parsing action table with parsing action conflicts.
I was ...
0
votes
2answers
44 views
Are Context Sensitive Languages Turing Complete? [duplicate]
Related questions:
Can regular languages be Turing complete?
Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?
https://stackoverflow.com/questions/14589346/is-c-...
2
votes
3answers
125 views
concatenation of context sensitive and context-free is context sensitive or not?
Assume that $L_1$ is context sensitive language and $L_2$ is context free language, is the language $L_1 * L_2$ context-sensitive or not?
I almost sure that is not, but can't prove it.
2
votes
1answer
38 views
Regularity of infinite concatenation
It is well-known that an infinite union of regular languages is not necessarily regular, since every language can be written as a union of singletons. What about infinite concatenations?
Let $\{ L_z :...
2
votes
1answer
43 views
How to reduce EQU to UNI?
Let $$\texttt{EQU}=\{u\#v \mid T(M_u)=T(M_v)\} \\
\texttt{UNI}=\{w \mid T(M_w)= \Sigma^*\}$$
How can you prove $\texttt{EQU} \leq \texttt{UNI}$?
The idea I have so far is, to simulate the TM that ...
1
vote
1answer
37 views
Description for languages that can be solved in time(n)?
How can one describe all languages that are in
$\mathrm{TIME}(n)$?
It can't be all the regular languages only, as for example $L = \{a^n b^nw \mid w \in \Sigma^* \land n \geq 1\}$ is not regular but ...
3
votes
1answer
45 views
How to reduce $\{w \mid |T(M_w)| \geq 42\}$ to the halting problem?
For a string $w$, $M_w$ denotes the Turing machine whose encoding is $w$.
I want to reduce the language $L=\{w \mid |T(M_w)| \geq 42\}$ to $H_0 = \{w \mid M_w \text{ halts on } \epsilon\}$, but I ...
2
votes
2answers
31 views
Examples of infinite sets of regular and non-regular languages that their union is regular and non-regular
I have been looking around for a good source to answer the following question.
Have read a few different sources but have not found the answer I was looking for.
The question is:
Give an example ...
2
votes
2answers
48 views
Turing machine reduction task
I am having trouble solving the following task:
Given is the language $$D=\{ \langle M, w \rangle \mid \text{$M$ is a Turing machine and $M$ enters all states on input $w$}\}$$
Prove that $D$ ...
3
votes
1answer
49 views
Is $\{ w_1cw_2 \mid w_1 ≠ w_2 \}$ a context-free language?
Is the language $L_1 = \{w_1cw_2 ~|~ w_1,w_2 \in \{a,b\}^{\ast} \text{ and } w_1 \neq w_2\}$ a context-free language?
It certainly isn't regular, but is it context free?
I'm having trouble creating ...
2
votes
1answer
61 views
Finding a regular expression of a language
Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^*b^*$, which their length is a product of 3 (meaning their length is divisible by 3).
...
0
votes
1answer
37 views
Prove or disprove the following proposition $L_1^*∪L_2^*⊆(L_1∪L_2)^*$ [duplicate]
$L_1^*∪L_2^*⊆(L_1∪L_2)^*$
I actually disproved the opposite proposition $[(L_1∪L_2)^*⊆L_1^*∪L_2^*]$ and my intuition tells me that this is actually true... I tried to show that the combinations of ...
0
votes
0answers
19 views
What's the difference between ioco, uioco and tioco in Model Based Testing?
I'm learning about formal languages and Label Transition Systems (LTSs) and how to test systems using Model-Based Testing. Specifically, the paper Model Based Testing with Labelled Transition Systems ...
3
votes
3answers
101 views
Does $L_1L_2 = L_2L_1$ imply $L_1 = L_2$?
Let $L_1, L_2 \subseteq \Sigma^*$ be two languages, where $\Sigma$ is some finite Alphabet.
Does $L_1L_2 = L_2L_1$ imply $L_1 = L_2$?
What if $L_1$ and $L_2$ are regular languages?
Can you give ...
2
votes
1answer
45 views
Show that the following language is undecidable
$\{ M \mid M
\text{ is a machine that runs in }100n^3 + 300\text{ time }\}$
I am currently stuck with this one. I thought of reducing HALT to M as the reduction seems legitimate to me: if the first ...
0
votes
0answers
13 views
building turing machine for busy beaverproblem
I have tried to build a turing machine for busy beaver problem that has BB(2,3) two variables and three variables but i am not sure if its correct or it needs any changes
3
votes
1answer
63 views
Language whose intersection with a CFL is always a CFL (2)
This is a follow-up to this question, which asks for an example of a non-regular language $L$ which satisfies the following condition, intersection resilience:
If $L'$ is context-free then so is $L ...
-1
votes
1answer
21 views
Is there any tiny tips to find counter example string for proving some language is not a CFL? [duplicate]
When I prove some language is context free, It is too hard to find example string.
Is there any tips? It takes too many time or eventually give up.
3
votes
1answer
25 views
Proof emptiness for PDA is $\mathcal{O}(n^3)$
It is well known that the emptiness problem vor PDAs is in $\mathcal{O}(n^3)$. I couldn't find a good paper proving this theorem. Furthermore a proof for VPAs would be fine for me as well if that is ...
0
votes
0answers
36 views
What does pump down means in this solution?
Problem text (from Sipser's "Introduction to the Theory of Computation"):
2.42 Let $E = \{1,\#\}$ and $Y = \{ w \mid w = t_1\#t_2\# ...... \#t_k \, \text{for $k \geq 0$, each $t_i \in 1^*$, and $...
1
vote
1answer
29 views
Closure properties of a non-regular language under complement? [duplicate]
Assume I have L1 which is a regular language, so we know since regular language is closed under complement, the complement of L1 is also a regular language.
But let's say if the complement of L1 is a ...
2
votes
1answer
20 views
Does |xy| ≤ p in the pumping lemma count for all i?
While learning about the pumping lemma, I came across the following question:
Given the language L is $ a^n(0|1)^* $ with $ c_0 \cdot c_1 = n $, where $ c_0 $ indicates the amount of zeros present, ...
5
votes
1answer
234 views
How to prove the emptiness of intersection of two context free languages is undecidable?
Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful.
Do you maybe ...
0
votes
0answers
25 views
finding grammar for language with 2^n same characters [duplicate]
Disclaimer: This is a homework question.
Given the language $L=\{a^{2^n}| n\in\mathbb{N}\}$:
1. find a corresponding grammar
2. give a derivation of $a^{2^3}$
3. In which Chomsky hierarchy is this ...
0
votes
0answers
33 views
Find PDA for CFL = {x#y | |x| = |y| and x ≠ y} [duplicate]
I am studying push down automata.
When I read a solution for showing $L = \{x\#y \mid x \neq y, x,y \in \{0,1\}^*\}$ is a CFL, I could understand $L = L_1 \cup L_2$, $L_1 = \{x\#y\mid|x| \neq |y|\}$, ...
0
votes
0answers
12 views
About Specification of PDA
I was learned NPDA is specified by a tuple $P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F) $,
$Q$ is a finite set of states
$\Sigma$ is a finite set of input symbols (input alphabet)
$\Gamma$ is a finite ...
1
vote
1answer
27 views
How to draw an LTS based on the parallel process “|” in CCS Milner's logic?
I'm trying to provide a Hennessy-Milner logic formula for CCS expressions that are not (strongly) bisimilar. An example with a sketch:
For each of the following CCS expressions, decide whether ...
1
vote
1answer
69 views
I have trouble translating Turing machine language, can you help me break down language notation to English?
My problem is I don't have many issues with creating a Turing machine state table when given a string such as 01101, my issue arises when I am presented with a problem which requires the Turing ...
3
votes
2answers
113 views
Prove $\{abc : a+b=c\}$ is not context-free using pumping lemma
I have the following alphabet:
$Σ = {0, 1, . . . , 9}$
and the Language $L$ defined as:
$L = \{ abc | a + b = c\} $
where substrings $a$, $b$ and $c$ are interpreted as ordinary integers.
My answer ...
0
votes
1answer
55 views
Show that CFG is not a LR(1) Grammar
Let G b the following CFG (Where S is the start symbol):
S→aB|aDc
B→bBc|c
D→bc|c
(a) Show that G is ambiguous.
(b) Show that G is not an LR(1) grammar.
(c) ...
1
vote
0answers
26 views
Computational power of quantum finite automata
I am preparing some lecture notes on the computational power of quantum finite automata (QFA). I am a bit confused about which models of QFA are stronger and which models are weaker than standard ...
1
vote
1answer
26 views
What is the relation between an algorithm and its implementation at the level of code?
Is there any isomorphism or equivalence relation? What strictly bind these two together?
1
vote
0answers
62 views
Law as a computer science problem?
For a long time, computer scientists and logicians have noticed that law (statutes, contracts, adjudication, etc), has some similarity with formal logic and programming languages, and have approached ...
0
votes
0answers
27 views
Law and contracts as “programs” executed by human brains
Note: This question is NOT about using computers/AI in legal practice.
I found a paper (pdf here) that makes the analogy between law and computer programming:
Laws and contracts are programs/...
0
votes
2answers
45 views
Convert this language to Context Free Grammar
I'm having trouble understanding how to convert this language to context free grammar.
$\{a^ib^jc^k\mid i > k, 0\le j \lt3, k \ge 0\}$
Part im getting stuck on is how to deal with a and c, ...
2
votes
1answer
98 views
Language to Generate Powers of 2 Using a Language Containing Decimal Numbers
For this question, I have the alphabet $\Sigma=\{0,1,2,3,4,5,6,7,8,9\}$. I also have the language $L$ over $\Sigma$ described as the language such that the strings $w$ contained in $L$ are powers of 2 ...
0
votes
2answers
87 views
CFG for the language L ={a^n w | w \in {b,c}^*, n= count of b.c in w. }
$L =\{a^nw \mid w \in \{b,c\}^*$, $n=$ #$_b$ + #$_c$$\}$
$\bullet $ #$_b$ denotes the number of $b$'s in $w$
$\bullet $ #$_c$ denotes the number of $c$'s in $w$
I have some trouble designing a CFG ...
3
votes
1answer
58 views
Why isn't DIV necessarily in P? [duplicate]
In my formal languages class, we discussed DIV, defined as following:
$\mathrm{DIV} = \{\langle a,b\rangle : \text{$a, b \in N$ and $a$ has a divisor $d$ for some $1 < d \leq b$ }\}$
($\langle\...
2
votes
2answers
59 views
Operator name in LL(1) computation
I'm working from a definition of the LL(1) property of context-free languages in order to build a LL(1)-computer, i.e., a program capable of determining whether a given context-free language is in LL(...
0
votes
1answer
36 views
What is the minimun type of logical system that recognizes if a formalized sentence is a well-formed formula thus reducible to the boolean value?
The formula, in the old way of using it, can contain symbols in order and a mixture that does not meet the criteria of correctness (i.e. arbitrary symbols do not form a well-formed formula (WFF) and ...
0
votes
3answers
85 views
Define a finite automaton accepting the language below [duplicate]
$\{ w∈(a,b)^\ast | w $ does not contain '$ab$' as a subword $\}$.
About questions like this, I always want to construct the regular expression for it, then convert the regular expression to a finite ...
