Questions related to formal languages, grammars, and automata theory
2
votes
0answers
13 views
Permutation of words that have matched parentheses
Let $L$ denote the (context-free) language of matched parentheses over the alphabet $\Sigma$. Consider the following problem:
Input: words $x_1,\dots,x_n \in \Sigma^*$
Question: does there exist a ...
3
votes
1answer
41 views
Is the symmetric difference of a non regular language L and a finite language f non regular?
The symmetric difference of $L_1$ and $L_2$ is defined to be: $(L_1-L_2) \cup (L_2-L_1)$.
Problem: I’m trying to prove that given L a non regular language and F a finite language there symmetric ...
1
vote
1answer
35 views
Proof that (A ∪ B)∘C = A∘C ∪ B∘C where A, B and C are languages
How can I prove this identity of languages?
My aproach is the following:
Let A, B and C to be languages, and let x to be an arbitrary string.
(A ∪ B) ⇒ x ∈ A ∨ x ∈ B
How do you proceed?
0
votes
1answer
44 views
Define a grammar to emmulate chess rules
Is it possible to define a 《chess language》:
language={alphabet = {(chess pieces, squares of chess board)}, grammar={rules of movement of pieces over the board}}?
I looked online but I cannot find a ...
1
vote
1answer
44 views
Formal grammar with variables for consistent substitutions
In a rewriting system, suppose the production rule S→xAyAz (or <S>:=x<A>y<A>z, in BNF), where S and A are ...
1
vote
1answer
27 views
Contradiction in regularity of a language
Lets say we have $L_1$ which contains all binary numbers divisivle by 2 but not by 4. I would say this language contains all words with a 10 at the end. Ive found a regular grammar $G$ with $L(G) = ...
1
vote
2answers
43 views
Is two arrows on each state necessary in DFA? [duplicate]
In DFA, is two arrows on each state necessary?
Or it depend on language alphabets? I mean if there is $\Sigma = \{a\}$ then there should be one arrows on each state.
OR if there are $\Sigma = \{a ,...
1
vote
0answers
11 views
Generating valid sentence with respect to attribute grammar
Given a context free grammar, both the algorithm for determining whether a given string is grammatical and the algorithm for producing a grammatical string in that language are well understood. To ...
2
votes
1answer
241 views
Determining if given languages are regular or recursively enumerable
I came across following problem:
Suppose $L_1$ and $L_2$ are two languages, $M$ is a Turing machine
$L_1 =\{M|M$ accepts at most 2016 strings$\}$
$L_2=\{M|M$ accepts at least 2016 strings$\}$
...
0
votes
1answer
33 views
Context-free grammar for $L=\{0^n1^{2n} \mid n \geq 0\}$ [closed]
How can I express this language $L = \{0^n 1^{2n} \mid n ≥ 0\}$ as a context-free grammar?
I am new to this field and I am not sure what should I do. Please help me.
0
votes
1answer
30 views
Different context-free grammars for the same language
In context-free grammar, are both the following grammars correct for the same language?
$$L = \{a^mb^n : m, n \in N_0 \text{ and } m \ne n\}$$
(grammar one)
$S \to S_1 | S_2$
$S_1 \to A_1B_1$
$...
0
votes
3answers
68 views
Concatenation of language to itself zero times
I was solving this question:
Which of the following statement(s) is/are false?
$L^0=\{\epsilon\}$
$|L^0|=0$
The answer given was None. That is, none of these statements are false and ...
-1
votes
0answers
17 views
What is relation between Deterministic context-free language and LL(k) languages?
Does for every DCFL P there exists some LL(1) grammar G such that L(P) = L(G)?
1
vote
1answer
38 views
“Or” in regular expressions
I'm a bit new to automata theory, I'm sorry if this question is a bit too simple. If this question has been answered somewhere already, please point me to it.
One basic problem I wanted to solve was ...
1
vote
1answer
44 views
Understanding facts about regular languages, finite sets and subsets of regular languages
I am aware of following two facts related to two concepts: regular languages and finite sets:
Regular languages are not closed under subset and proper subset operations.
It is decidable ...
1
vote
1answer
23 views
polynomial time reducibility - $L_{2} \notin \textbf{P}$ and $L_{1} \leq_{p} L_{2} \implies L_{1} \notin \textbf{P}$
If we have two languages $L_{1} \subseteq \Sigma^{\ast}_{1}$ and $L_{2} \subseteq \Sigma^{\ast}_{2}$
I proved that when $L_{2} \in \textbf{P}$ and $L_{1} \leq_{p} L_{2}$ then $L_{1} \in \textbf{P}$
...
1
vote
1answer
26 views
Difference between regular language and context free language
What is nature of difference of regular language and context free language?
My guess is
RL - CFL = RL
CFL - RL = CFL
Am I correct with this?
1
vote
1answer
46 views
Both a language and its complement are not context free
Is there a language $L \subseteq \{a\}^*$ such that both $L$ and its complement are not context free?
2
votes
1answer
63 views
Understanding application of Arden's theorem to find regular expression
I learnt Ardens theorem and its usage as follows:
Ardens Theorem
Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$
does not contain null string, then $R = Q + RP$ has a ...
2
votes
1answer
45 views
How to prove that $L = \{a^n b^m a^n b^m \mid n,m \ge 0\}$ is not a CFL?
I'm stuck with the proof. I've tried Ogden's lemma but it doesn't seem to help.
The problem is: Let $N$ be the constant of Ogden, let $z = a^N b^{N+1} a^N b^{N+1}$, and $z = uvwxy$. Now I should ...
-1
votes
1answer
28 views
Regularity under set difference
Let L be a regular language.
Then $\Sigma^{*} \backslash L^{*} = (\Sigma^{*} \backslash L)^{*}$
How do I prove it is wrong?
1
vote
1answer
44 views
Context Free Grammar $L = \{a^i(b+c)^jd^k | i<j+k; i,j,k>0\}$
I'm trying to design a CFG that accept the words of the following language:
$$L = \{a^i(b+c)^jd^k \mid i<j+k; \quad i,j,k>0\}$$
My first approximation would be to do $i = j+k$ as something ...
1
vote
3answers
49 views
Infinite Union operation of Formal Languages
Is every formal language not closed under infinite union operation ?
I know that Regual Languages are not closed under infinite union operation and I have counter-example for it but I don't have any ...
0
votes
0answers
19 views
Number of non deterministic finite automata that can be constructed for $n$ states and alphabet with $m$ symbols
I came across the fact that
The number of DFAs that can be constructed for $n$ number of states and alphabet containing $m$ symbols is $n\times (\color{red}{n}^m)^n \times 2^n$
So I was wondering ...
3
votes
1answer
79 views
Identification of Formal Language
$$L = \{a^{m+n}b^{m+k}c^{n+k}\mid m,n,k\ge 1\}.$$
Is $L$ DCFL or not?
According to me it should be DCFL since we can write $L$ as $\{a^{n}a^{m}b^{m}b^{k}c^{k}c^{n}\mid m,n,k\ge1\}$. So, now after ...
0
votes
0answers
17 views
Subclass of nonregulsr CFL's, closed under complementation? [duplicate]
Whether there exists a subclass of nonregular CFL's closed under complementation?
5
votes
2answers
72 views
Prove $\{xy: x \in A \land y \in B \land |x| = |y|\}$ is context-free
This is problem 2.44 from Introduction to the theory of computation by Michael Sipser.
If $A$ and $B$ are languages, define $A \diamond B = \{xy: x \in A \land y \in B \land |x| = |y|\}$
...
0
votes
0answers
18 views
Transform grammar into LL(1) left-associative
I was looking on some old exam questions for a course in my university, and stumbled upon an exercise that asked for the following: The starting grammar was this:
...
4
votes
1answer
36 views
General version of pumping lemma for regular languages, how many partitions to consider
The pumping lemma for regular languages states, that one should consider a string $w = xyz, w\in L$, that is, every possible division of $w$ into $xyz$.
The article on wikipedia says, that this ...
1
vote
0answers
46 views
Proving a language is not context-free using the pumping lemma
I had a question regarding the use of the pumping lemma for a particular language I came across. I feel like I have almost solved it, but have gotten stuck on the last steps and wanted some advice. ...
0
votes
1answer
20 views
Why is this grammar an LL(2) grammar?
I had a question regarding LL($k$) grammars. I came across a problem that I attempted to solve, but my answer varied from the solution and I wasn't sure why.
$$L = \{a^{n + 2}b^mc^{n + m}\ :\ n \ge 1,...
0
votes
1answer
92 views
Does adding S->SS in a context-free grammar change the language to its Kleene star?
Let $L$ be the language generated by a context-free grammar whose start variable is $S$. Does adding $S \rightarrow SS$ in this grammar creating language $L^*$, why? What about grammars in Chomsky ...
2
votes
0answers
26 views
Can pushdown automata be without epsilon transitions? [duplicate]
Are pushdown automata without $\varepsilon$-transitions as powerful as those with them? Intuitively, if we need to make such a transition, we could just add the letters on the next transition we take, ...
1
vote
1answer
28 views
Proving that Pre(L) is regular using automatas: Should I prove that Pre(L) is the semantic of the new automata?
Let $L$ be a regular language, and $Pre(L)$ be the set of all words that are prefix of some word in $L$. Prove that $Pre(L)$ is regular.
My proof:
Let $M = (\Sigma, Q, \delta, q_0, F)$ be an ...
1
vote
2answers
38 views
CFG where u has same number of 1s as v [closed]
$$L=\{uv\in\{0,1,2\}^*\mid u\in\{0,1\}^*,v\in\{1,2\}^*, \text{ and }u\text{ has the same number of 1s as }v\}.$$
Here is my attempt solution, but it is not completely correct, any hint is appreciated
...
4
votes
1answer
57 views
How does TLC check liveness properties?
The paper "Model Checking TLA+ Specifications" published in 1999 explained how TLC (Temporal Logic Checker) checks safety properties written in TLA+ developed by Lamport. At that time, TLC did not yet ...
1
vote
1answer
41 views
Is there a context-free grammar for $L = \{a^{2^n}| n \geq 1\}$? [duplicate]
I was trying to find a cf-grammar for $L = \{a^{2^n}| n \geq 1\}$ but I cannot seem to find one. Is there a cf-grammar or does it not exist because of the quadratic-exponent?
8
votes
5answers
2k views
Finite state automata: final states
In our programming language concepts course, our instructor claimed that it's okay for a final state to lead to another state in a finite state diagram.
But this seems to be a fundamentally ...
0
votes
2answers
52 views
How would a Turing Machine recognize n consecutive characters
I have difficulties understanding how a TM could count number of characters. I have this problem where the input is made out of characters $\{a, b\}$ and I need to accept if there are $n$ characters ...
-1
votes
2answers
46 views
Context-free grammars for two languages
How do I write context-free grammars for the following languages?
$B_2 = \{0^n1^n \mid n > 0\} \cup \{0^n1^{2n} \mid n > 0\}$
$B_3 = \{a^nb^mc^k \mid k = n+m\}$
Can someone help me? I'm not ...
3
votes
1answer
178 views
This doesn't seem like a valid regular grammar; my instructor says it is
The following is a screenshot of a lecture slide from my programming language concepts course:
According to Wikipedia and other sources, a regular grammar is one that is either left linear or right ...
0
votes
0answers
13 views
Non-context free languages with word degree [duplicate]
I have stumbled across these 2 problems
$L_1= \{\alpha \mid w \in \{a,b\}^* | \alpha $ has exactly 2 b's$\} $ ,prove that $L =\{ \alpha^n | \alpha ∈ L_1 ,n \ge 0 \}$ is not context free
Given : $...
1
vote
1answer
42 views
Which word to pump in pumping lemma?
Let say we have a Language $L = \{0^m1^n \mid m,n \geq 0 \land m \neq n \}$. If I want to use the pumping lemma to disprove that the language is regular or context-free, how do I choose the word in ...
1
vote
1answer
36 views
DFA complexity of reverse of language recognized by “maximal” DFA
Let's assume that DFA $A$ over the alphabet $\Sigma$ and with states $Q$ is maximal if for every function $f\colon Q\rightarrow Q$ there exists such word $w \in \Sigma^{*}$, that $q \cdot w = f(q)$ ...
-2
votes
1answer
49 views
Does $R(L_1\cdot L_2)=L_2\cdot L_1$? [closed]
Does $R(L_1\cdot L_2)=L_2\cdot L_1$?
Where $R$ is the reverse.
I can't think about counter example
0
votes
0answers
12 views
How to convert this CFL into a CFG? [duplicate]
I'm trying to convert the following context free language into a context free grammar.
$L = \{a^i b^j c^k \,|\, i+2j=4k;\, i, j, k ≥ 0\}$
I am struggling given the fact there is a large number of ...
3
votes
2answers
77 views
Why is the start symbol “not allowed” on the right hand side in Chomsky normal form?
I had a question regarding CNF (Chomsky normal form) in formal language theory.
I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow ...
0
votes
1answer
46 views
Context-free grammar from language
I'm trying to come up with a context-free grammar for the following language:
$$L = \{a^mb^nc^{m+n}\mid 0 \le n \le m\}$$
My thinking is that i can rewrite this to
$$L = \{a^mb^nc^nc^m\mid 0 \le n \...
0
votes
0answers
23 views
Create a transition system where every sequence has at least twice as many $a$'s than $b$'s
Create a transition system with edges $a$ and $b$ and an initial
state, such that for all possible sequences, you have that: The amount
of $a$'s in the sequence is at least twice as much as the ...
1
vote
1answer
36 views
Determining whether $L^*$ is a finite union of $L^n$ for unary regular $L$
Give an algorithm that, given an NFA over a one-letter alphabet, determines whether the language it generates has the property that for some $n$, $$ L^* = \bigcup_{k=0}^n L^k. $$
I need some tips how ...
