Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
2
votes
2answers
50 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
53 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
88 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^*$, whose length is a multiple of 3. Obviously $(aaa)^*(bbb)^*$ is one of the options, ...
0
votes
1answer
39 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
36 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
102 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
51 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
14 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
65 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
22 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
28 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
40 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
34 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
22 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
240 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
34 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
14 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
36 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
70 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
120 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
67 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
28 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
27 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
65 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
28 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
57 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
100 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
94 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
59 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
60 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
38 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
88 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 ...
2
votes
2answers
35 views

Why can we (apparently) implement CFG parsers only using (N)DFAs?

I am working on a project in which I need to parse files written in different DSLs. One important feature of these languages is that most of them allow blocks to be nested. For parsing those files I ...
1
vote
0answers
33 views

Characterization of NFA whose equivalent (minimal) DFA has exponential number of states

(I don't know if there are standard names for this, so) Let's say that a Nondeterministic Finite Automaton (NFA) is $n$-expansive if it has $n$ states and any Deterministic Finite Automaton (DFA) ...
2
votes
1answer
42 views

Finding an unambiguous grammar of a language provided by a CFG

I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman. In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar ...
1
vote
1answer
41 views

Can the complement of a context-free language be regular?

I know that the context-free language is not closed under the complement , and the result could be context-free language or non-context free language but my question is : is it possible of the ...
0
votes
0answers
67 views

How to find the minimum number of states of a deterministic finite automaton accepting a given language [duplicate]

Let $L$ be a language over $\Sigma$. And $\Sigma = \{0,1\}$ is a set of input alphabets. $L = \{ w \mid w \in \Sigma^*, \text{ where $w$ is a string with numbers of 0s divisible by 3 and number of ...
2
votes
1answer
36 views

Construct a decidable set $B$ such that $B \neq A_w$ for any $w \in \Sigma^\star$

I've been stuck on this problem for a while. Any hints would be appreciated! Let $A \subseteq \Sigma^\star$ be decidable. Given $w \in \Sigma^\star$, define $$A_w = \{x \in \Sigma^\star\:|\: \langle ...
1
vote
1answer
312 views

Language whose intersection with a CFL is always a CFL

Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L \cap L_0$ is context-free, then $L$ is regular. I haven't managed to prove this, but I'm ...
1
vote
1answer
72 views

Prove that $L = \{ xy \in \{a , b \}\textbf{*} \mid |x|_a = 2|y|_b \}$ is not regular

Prove that $L = \{ xy \in \{a,b\}^* \mid |x|_a = 2|y|_b \}$ is not regular. I have already tried to prove it by using the pumping lemma and reduction to absurdity, but have been unsuccesful on both. ...
1
vote
1answer
50 views

How to correctly describe this action, deleting an edge that “shortcut” some vertices

Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below: 1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in ...
1
vote
1answer
52 views

Brzozowki's algorithm doesn't work for this corner case

I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example: In this DFA, $S_0$ and $S_1$ are nondistinguishable and ...
0
votes
1answer
67 views

how can one counter machine accepts a^n b^n c^n?

It is mentioned in Which languages are recognized by one-counter machines? that one counter machine can accept $\{a^n b^n c^n\mid n\geq 0\}$. Can someone please explain how this is done?
-3
votes
1answer
59 views

Context Sensitive Grammar for the language $\{a^n b^n c^{2+k}\mid n \ge 1, 0 \le k\le 1\}$ [closed]

I'm studying for my final exam and come up with this exercise with no idea how to find the production rule of this grammar. I need help. Thanks all of you! :)
2
votes
2answers
116 views

Can a TM recognize whether another TM recognizes a non-empty language?

Let $$L_1 = \{\langle M\rangle\mid M \text{ is a Turing Machine and }L(M)\ne\emptyset\}.$$ Is $L_1$ recognizable? If so, can you give me a pseudo-algorithm? My attempt: I wanted to study ...
1
vote
0answers
23 views

Proving existence of a language $L\in DTIME(n^{\log n})$ which is not in $Avg-P$

I'm struggling with the following question: Define $Avg-P$ the class of all languages $L$ for which there exists a polynomial time Turing Machine $M$ such that for every $n$, for all but $\frac{2^n}{...
0
votes
1answer
87 views

Finding two languages satisfying conditions

Let $$E_{TM} = \left \{ \langle M\rangle \mid L(M) = \emptyset \right\}$$ Prove that there are two languages $L_1, L_2$ such that $L_1, L_2 $ are infinite. $L_1 \cup L_2 = E_{TM}$ $...
1
vote
1answer
128 views

For any two regular languages A, B, show that {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free

Basically I'm wondering if the concatenation of two equal length string is context free. I've seen multiple proofs of this online using PDAs but we aren't covering them in my automata course and my ...
0
votes
2answers
47 views

Regularity of a language contains more 1's than 0's

The language of all bitstrings with more 1s than 0s, i.e., $ A = \{x: 2\Sigma_{i}^{|x|} x_{i} > |x|\}$ is regular. I know I should apply Pumping Lemma and the proof as well, what I cannot ...