Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,455
questions
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$...
