Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
0
votes
0answers
80 views

context-free language : if yx belongs to cfl then xy is also cfl [duplicate]

I faced a problem. What is the proof to say that if yx is in a Context-Free Language we can say that xy is also in a context-free language. C is a Context-Free Language. I think we can use the PDA ...
0
votes
1answer
64 views

Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }

I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }. This is really confusing me, I'm having trouble with ...
1
vote
1answer
35 views

Designing CFG that accepts $b^m a^n$ ($m ≤ n$)

I am trying to design a CFG that generates the language $\{a^k b^m a^n a^k \mid m \leq n\}$. However, I am having trouble with the $b^m a^n$ where $m \leq n$. How do I solve this?
0
votes
1answer
52 views

Is the empty string and some words of even length are elements of this set?

$L = \{w \in \{a,b\}^*| \text{the first, the middle, and the last characters of $w$ are identical}\}$. I have my answers, but I need confirmation: Is the empty string $\epsilon \in L$? Yes. Reason: ...
2
votes
1answer
119 views

When our two-state PDA constructed from CFG is non-deterministic PDA?

We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule ...
0
votes
1answer
28 views

Shortest unambiguous representation of a graph over an alphabet

I just started reading a book on theoretical computer science and here are a couple of beginner questions about graphs, which I am struggling to answer: Given the graph with the matrix ...
2
votes
1answer
101 views

Difference between assignment, binding, and substitution?

I am trying to understand the difference of assignment, binding, and substitution. I know the three things are related, but to me it's not exactly clear what word refers to what. Example, illustration,...
-1
votes
1answer
34 views

How to find the language and create Push down automaton if the A is continuously looping ? and will PDA accept L produced without A

Let us consider the following Context-Free Grammar G = ({S,A,B,C,D},{a, b}, S, P) with production rules P: S → SSA | Bb A → BSA B → A | Cb C → AD | Cb | ɛ D → a | b | ɛ Let L be the language ...
0
votes
2answers
53 views

PDA with more than one initial state

I'm wondering if PDAs with more than one initial states are also accepting context free languages. If found that question on this site about NFAs and would like to know if this answer is also valid ...
-1
votes
1answer
35 views

Proof for palindrome grammar by induction

I can't seem to find a solution to the following question. Given the following grammar for palindromes: $$G_{pal}=\{\{a,\dots,z\},\{P\},P,R\},$$ with $R$ consisting of the rules ...
1
vote
2answers
215 views

Given regular language $L$, is $L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length} \in L \}$ regular?

I was given a question and don't really know to solve it. Given a regular language $L$, is the following language also regular? $$L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length ...
0
votes
0answers
365 views

Converting CFG to GNF problem

I have a big problem with converting GNF example. This is my CFG $ S \to AS\mid BS\mid \lambda\\ A \to aC\mid BCA\mid c\\ B \to AB\mid b\mid \lambda\\ C \to S\mid d $ I simplified the CFG by ...
1
vote
1answer
137 views

Check if language is decidable

I would like to determine if the following language is decidable or not. L = { w $\in$ $\Sigma^*$ | $T(M_w)$ is recognized by a Turing machine with at most 42 states}. I know that every finite ...
2
votes
1answer
39 views

Decide if a language has a word of a given size

Suppose that $L$ is some language over the alphabet $\Sigma$. I was asked to show that the following languages is decidable: $$L' = \{w \in \Sigma^* | \text{ there exists a word } w'\in L \text{ ...
0
votes
0answers
20 views

Are DPDAs accepting on final state equivalent to DPDAs accepting on empty stack equivalent? [duplicate]

Say I have a string x that is accepted by some DPDA P that accepts empty stack. Intuitively it's seems impossible for P to accept any string x.y for any y != epsilon. The below DPDA accepts on final ...
1
vote
1answer
28 views

Formal defintion of SET-PARTITION as a language

I am not quite sure howto define SET-PARTITION as a language as in Sipser. Is it $$ \left\{ \langle S,A,B\rangle \;\middle|\; (A,B) \text{ is partition of } S \text{ and } \sum_{n\in A} n = \sum_{n\...
1
vote
1answer
43 views

Languages A, B ∈ NP-complete such that A⋃B = Σ*

I'm pretty new to complexity theory and it seems like I stuck with this problem. We should find language $B$ such that it accepts any words rejected by $A$ but in that case, it seems that $B$ is a ...
0
votes
2answers
146 views

Are all language over $\Sigma= \{0\}$ decidable?

I have problem in determine whether it is decidable or not, can somebody help me please
0
votes
1answer
34 views

Is that true that A is decidable if A$\le_m$A complement? [duplicate]

A is decidable if A$\le_m$A complement Can i think that it is true because decidable is close under complement, so if A complement is decidable, so is A
-2
votes
1answer
141 views

Grammar with a long derivation generates an infinite language

Let $G$ be a CFG in Chomsky normal form that contains $b$ variables. Show that if $G$ generates some string with a derivation having at least $2^b$ steps, then $L(G)$ is infinite. This question is ...
1
vote
1answer
55 views

CFG for a given languague

Give a CFG for the languague L = $ \{ 1^n +1^m = 1^{n+m}| n,m \in N_{0}\} $ , with the alphabet $\Sigma =\{1,+,=\}$. I am currently trying to solve the given task, I thought a good way is to split ...
0
votes
1answer
128 views

Is there an undecidable language that is mapping reducible to its complement?

Is there an undecidable language A that is mapping reducible to its complement? If it is possible, since A is an undecidable language, so A's complement must also be an undecidable language. But i don'...
1
vote
1answer
144 views

How to prove language $L=\{a^{i}b^{j} : i \leq j^{2}\}$ is not CFL using Pumping lemma?

I'm trying to found a way how to prove this language is not context free. Using pumping lemma I'm halfway done. Consider word $a^{n^2}b^n$. If you divide it into $uvwxy$ and have only $a$'s in $v$ and ...
0
votes
1answer
127 views

Same notation/terminology for union of sets and concatenation (Kleene star)?

For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology ...
-3
votes
1answer
42 views

Minimization of automata with dead state

I am supposed to minimize the following DFA automa, which contains dead state: But after the minimization of the automata, it stayed the same. Is it correct?
1
vote
1answer
61 views

Context free grammar for $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$

I try to find a context free grammar for the language $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$. There is a hint ...
0
votes
1answer
68 views

If $L1⊆L2$, and $L1\not∈RE$, is it possible that $L2∈RE$

If $L1⊆L2$, and $L1\not∈RE$, is it possible that $L2∈RE$ ? Also I find it hard to find languages that are not in RE at all, I've heard about Arithmetical hierarchy but we didn't really learnt it in ...
1
vote
1answer
51 views

Intersection of two particular languages

Here's the question: Compute the intersection of the following two languages: \begin{align} &L_1 = \{ a^{n+1} b^{2n} a^{n+1} \mid n \ge 0 \} \\ &L_2 = \{ w \in \{a,b\}^* \mid \#_a(w) + \#...
4
votes
2answers
76 views

Regular language as finite union of periodic sets

Is it true that every regular language can be expressed as a finite union of periodic sets? In other words, if $L$ is regular, then do there exist finite sets $A_1,\dots,A_n,B_1,\dots,B_n$ such that ...
0
votes
2answers
71 views

Is the following language is a context free grammar language?

The question is to determine whether L is a context free grammar language, what do you think?
0
votes
0answers
45 views

generate CFG from words that have even length and have at most two 0's

How to I generate a CFG from the language that have even length and have at most two 0’s L3 = {w ∈ {0, 1} ∗ | w is even length, 0<=2 } I feel stuck on meeting the criteria of maximum two 0s My ...
-2
votes
1answer
37 views

Computing FIRST and FOLLOW

Given the following grammar with terminals $VT=\{[,],a,b,c,+,-\}:$ $S \rightarrow [SX]|a$ $X \rightarrow +SY|Yb|\epsilon$ $Y \rightarrow -SXc|\epsilon$ This should be the FIRST function: $first(S) =...
1
vote
2answers
147 views

Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular?

Question is as follows: Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular? Thank you for any input.
1
vote
1answer
34 views

Language of context-sensitive grammar

I have the following context-sensitive grammar: $$ \begin{align*} &S \to xSy \mid a \mid b \\ &Xa \to aa \\ &Xb \to bb \\ &Y \to a \end{align*} $$ I know what it does, as it always ...
1
vote
1answer
24 views

Language of particular CFG

Let: $ G = <V, \Sigma, R, S >: \\ V = \{ S,A,B,C \} \\ \Sigma = \{0, 1\} \\ R: \\ S \to CSC|A \\ A \to 0B1|1B0 \\ B \to CB|\epsilon\\ C \to 1|0 $ I need to find the language (no need to ...
1
vote
1answer
33 views

More the number of for loops greater the problems solved

This is more a formal language theory question. Imagine a setting where you are given a very basic programming language where variable assignments etc are taken care of without any of the iteration ...
0
votes
0answers
26 views

If T is a Turing Machine, what are the languages Accept(T), Reject(T) and Loop(T)?

I have the following Turing machine: I am asked what are the langauges accept(T), reject(T) and loop(T). This seems to me a trivial question as from the looks of it, accept(T) is the language of all ...
-1
votes
2answers
83 views

L= { x=y+z| x,y,z are binary integer, and x is the sum of y and z}

The alphabet is {0,1,+,=}. I think it is a regular language since i can construct the NFA, But i want to make sure Thanks
-1
votes
2answers
116 views

CFG for language of words with odd many $a$ and exactly two $c$

I am trying to construct a context-free grammar for the language $$ L = \{ w \in \{a,b,c\} \mid w \text{ contains an odd amount of } a \text{ and there are exactly two } c \}. $$ I am currently stuck ...
2
votes
3answers
900 views

Bitwise XOR of regular languages

Is the language consisting of the bitwise XOR of elements of two regular languages still a regular language? For example, consider $$L=\{ x \operatorname{xor} y \mid x \in A, y \in B, |x|=|y| \},$$ ...
0
votes
1answer
184 views

Proof language A= { 0^i 1^j where j>(i mod 3), j ≥0 , i≥0} is regular language

$A = \{0^i1^j \text{ where }j>(i \text{ mod }3), i \geqslant 0, j \geqslant 0\} $ I know that A is a regular language, since we can construct the DFA or the NFA, but i dont know how to construct ...
0
votes
0answers
291 views

closure property on Recursively enumerable language

How to prove that recursive and recursively enumerable language is closed under reversal? Why recursively enumerable language is not closed under set difference? [But intersection of recursive and ...
-1
votes
1answer
267 views

Turing machine on input w tries to move its head past the left end of the tape

Consider the language $$ L = \{ \langle M,w \rangle \mid \text{$M$ on input $w$ tries to move its head past the left end of the tape}\}. $$ Prove whether L is decidable or not. I tried to prove ...
0
votes
0answers
9 views

Writing a Grammar to a Language [duplicate]

is there a general method or approach to writing grammars to a language? I do not want to describe the language I have to write a grammar to as I do not want a specific answer. I am looking for ...
3
votes
1answer
65 views

Is the language of palindromes context-free?

Is the language $\{ w=w^R \mid w \in \{0,1\}^* \}$ a context-free language? I am confused in deciding whether the language is context-free or not, that is one of my problems, I do a pumping lemma ...
1
vote
1answer
61 views

Languages such that DFA requires $\Omega(c^k)$ states but NFA needs only $O(k)$ states?

Given an alphabet $\Sigma$, let $c=|\Sigma|$. Can a set of languages $\{L_k\}$ be created, such that any DFA for $L_k$ has $\Omega(c^k)$ states and a NFA for $L_k$ exists with $O(k)$ states? I'm ...
0
votes
0answers
30 views

Understanding Subset construction in following example

In going through the paper, Synthesizing Runtime Enforcer of Safety Properties Under Burst Error, https://link.springer.com/chapter/10.1007/978-3-319-40648-0_6, where the example automata considered ...
0
votes
1answer
72 views

The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani, where I came across few statements ...
5
votes
2answers
618 views

Complement of a DFA without final states

Let $L_1=\{Q,\Sigma,q_0,\delta,Q\}$ be a DFA that accepts a language $L$ and where all the states are also final states. If we want a DFA that accepts the complement of $L$, we swap its accepting ...
1
vote
1answer
18 views

Clarifying Practicality and Usage of a DFA's Accepted Language

I was reading up on DFA's and their accepted languages when I stumbled across this: Let a DFA $M$ accept the language $L⊆Σ^∗$, DFA $M'$ accepts $P(L)=$ {$w∈Σ^∗|wy∈L$ for some $y∈Σ^∗$}. Since any $wy$...

1
3 4
5
6 7
50