Questions related to formal languages, grammars, and automata theory
1
vote
1answer
30 views
When is the concatenation of a language $L$ with $\Sigma^*$ regular?
I've been looking at questions about the regular concatenation of two languages; one question said that the concatenation of $\{0^n1^n|n\geq 0\}$ and $\Sigma^*$ was regular (over the alphabet $\Sigma =...
1
vote
1answer
32 views
Find equivalence classes of language $L = \{0^n1^n, n \in \mathrm{N}_0 \}$
I'm asked to find all equivalence classes of the language
$$L = \{0^n1^n, n \in \mathrm{N}_0 \}$$
We have the following definition:
$$(xR_Ly)\Leftrightarrow (\forall w\in \Sigma^* xw\in L \...
1
vote
1answer
26 views
CFG for language of all palindromes whose number of 1s is divisible by 3
The question is the following:
Construct a CFG for $L_2 = \{w ∈ {0, 1}^* \mid w = w^R\text{ and the number of 1’s in $w$ is divisible by 3}\}$.
I can construct a CFG for $\{w \in \{0,1\}^* \mid w =...
2
votes
1answer
61 views
Regularity of language of words containing a square
$$L = \{w\mid w\text{ contains a substring of form }yy\text{, where }y\text{ is any non-empty string}\}.$$ Is this language regular? We do not know what $y$ looks like in advance. And why is this ...
0
votes
0answers
11 views
How to create a context free grammar for the complement of the following language? [duplicate]
Let $L = \{xcx |x\in\{0,1\}^*\}$, the terminal symbols being $\{0,1,c\}$.
The complement would accept the following types of strings:
Strings with no c's, i.e. $\{0,1\}^*$
Strings with a single c, ...
0
votes
2answers
42 views
Can an alphabet be $\{ε\}$ or $\mathbb{N}$?
Hopcroft says it is a finite nonempty set of symbols.
$\varepsilon$ (empty string) is not an ordinary symbol.
$\mathbb{N}$ is not finite.
So, no to both?
On the other hand, I do not see why $\{\...
0
votes
0answers
17 views
Formal language vs. decidability problem [duplicate]
What is the difference between a formal language and a decision problem? The formal language definition (which I use) is: subset of Kleene's Hull over an alphabet.
The concept of decision problems is ...
0
votes
1answer
40 views
PDA to accept language with more a's than b's and c's
My question is similar to this one. I was wondering if a PDA exists, that accepts any words containing a's, b's and c's in a random order, where the total amount of a's is higher than the amount of ...
1
vote
1answer
38 views
Inductive approach on Kleene star proof
I'm having trouble proving the following: If $L_1$ and $L_2$ are languages then: $$(L_1^*L_2^*)^* = (L_1\cup L_2)^*$$
I could be on the wrong track here, but I figured an inductive approach is a good ...
3
votes
1answer
46 views
Find a regular grammar that generates language $L$
I have a language $L$ = {$vabu$ | $v$,$u\in \{a,b\}^*$, $|vu|_a = 0$ $($mod $2)$$\}$
where $|vu|_a$ is number of $a$ in $vu$.
I came up with these rules:
$\sigma \rightarrow aa\sigma | ab\xi$
$\...
2
votes
3answers
41 views
Given an CFG determine if $\varepsilon \in L(G)$
Given a context free grammar how am I able to determine if $\varepsilon \in L(G)$ ?
The only way I thought of is to systematically check if I can derive the empty word from the given grammar. (...
1
vote
1answer
69 views
Is the problem of determining whether a CFG generates a string in the form 0*1* decidable?
Given a grammar $G$, is it decidable whether $G$ generates any string in the form $0^*1^*$? Why?
I think it's undecidable but can't find any undecidable problem to reduce it to.
0
votes
2answers
119 views
Non-regular language whose prefix language is regular
I understand that prefix of a regular language is regular, but I am unable to get my head around this:
Give an example of a non-regular language $A ⊆ \{0, 1\}^*$ for which $\operatorname{Prefix}(A)$...
2
votes
1answer
41 views
Prove that every CFL has at least one infinite equivalence class
If we define the Myhill-Nerode relation on a CFL how can i prove that there is at least one infinite equivalence class?
0
votes
1answer
39 views
What is an infinite language?
I just started reading about formal language theory and what i have learnt so far that:
Alphabet is a finite set of symbols.
String/Word: is always finite.
Because a language is set of strings of ...
0
votes
1answer
41 views
Different iterations of regular expressions
A four-part question dealing with formal languages and regular expressions:
How many basic regular expressions (using only the rules 0/ϵ, 1/∅, *, +, and •) are there to match a given string?
How ...
0
votes
3answers
626 views
is this language regular and why pumping lemma doesn't work?
I was told that this language is regular but as I can show below, pumping lemma is not working for it. What am I doing wrong? Is this language really regular? Why?
0
votes
2answers
62 views
Does there exists a finite automata for the given language?
The question is simple and given as, $alphabets=\{a, b\}$, and language $L$ over them as:
$L = \{w: w \ € \{a, b\}^*, (n(a) - n(b)) \ mod \ 3=1\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of ...
5
votes
1answer
240 views
About the relationship between non-termination and inconsistency?
I've been trying to get into Agda and I noticed that it doesn't have recursion, which implies that it isn't Turing-Complete.
From what I could understand, if Agda had recursion, it would make itself ...
0
votes
0answers
25 views
Formal vs Semi-formal languages
Why is the ER Diagram considered a formal language while the UML diagrams are considered semi-formal languages ?
I came up with this question while studying a book about Software Engineering and i'm ...
1
vote
3answers
75 views
What is a non-ambiguous CFG for generating the set of natural numbers?
I'm trying to write a non-ambiguous context-free grammar that can generate the set of natural numbers, including the 0. My current solution is the following grammar:
$\mathcal{G}: S \rightarrow 0\ |\ ...
2
votes
1answer
119 views
Is there a polynomial time algorithm to tell if an NFA over an unary alphabet is universal?
Given an Nondeterministic Finite State Automaton with $n$ states over an unary alphabet, is there some algorithm to check if the automata is universal in time polynomial in the number of states?
I ...
2
votes
1answer
36 views
Proving formula for derivative of Kleene star
Prove that for any symbol $a$ and regular expression $r$ it is true that:
$$\partial a(r^* ) = \partial .a(r)(r^* )$$
My attempt:
Induction on regular expression $r$
Base cases:
1) $\...
2
votes
3answers
361 views
Are all finitely recursive context free languages parseable with a regexp?
Let's say I have a context free language. It can be recognised by a pushdown automaton. Chances are it can't be parsed with a regular expression, as regular expressions are not as powerful as pushdown ...
-3
votes
1answer
173 views
Is mathematics context-free?
Anyone who deals with mathematics knows intuitively that it is a different kind of thinking than ordinary common-sense thinking that intelligent people use every day to understand and make decisions ...
1
vote
2answers
21 views
How to determine maximum stack size of LL(1) parser?
I am generating an LL(1) parser generator for LL(1) grammars that have a maximum stack size when executed in the table-driven parser. Specifically, I'm parsing HTTP headers using a parser generated by ...
1
vote
1answer
41 views
Proving equivalency of regular expressions
x,y are regular expressions, prove this:
(xy+x)$^*$x = x(yx+x)$^*$*
(* in this expression is kleene star)
I am looking for a method that is applicable to prove such questions.
I know that proof ...
0
votes
1answer
41 views
Class of given language
The language given is:
$$L = \{\langle M\rangle \mid M \text{ accepts all strings of length at most 5} \}$$
I have to find the class to which this language belongs.
Now according to my intuition, ...
1
vote
1answer
80 views
How many languages exist over the following alphabets?
(a) We have alphabet $\Sigma=\lbrace 1 \rbrace$, $\Sigma=\lbrace a,b \rbrace$ and (b) also an alphabet with size $k$ and words with length $n$.
For the first two alphabets in (a), we know that there ...
0
votes
1answer
42 views
Examples of non-sparse languages
All I could find is an example of sparse language.
I understand that I need to design a language whose all strings generation should not be bounded by a polynomial function, but I feel all the ...
1
vote
1answer
31 views
Words generated by CFG whose parse tree contain even number of $X$
Let $G$ be a context-free grammar with set of terminals $A$. Let $X$ be a non-terminal in $G$. Is the language of words over the alphabet $A$ with a syntax tree in which the non-terminal $X$ appears ...
0
votes
1answer
51 views
Is there a proof that shows why DFAs can't be used to show the concatenation of two regular languages?
Sipser goes on to show that regular languages are closed under concatenation using NFAs. His proofs typically use NFAs to prove closure under the operations.
Is there an alternative proof that goes ...
1
vote
2answers
26 views
Language equivalent states in a deterministic parity automaton
Given a deterministic parity automaton $\mathcal{A}$ with state set $Q$ and a state $q \in Q$, we denote with $\mathcal{A}_q$ the same automaton with initial state $q$. Two states $p$ and $q$ are ...
2
votes
1answer
47 views
Context formal language recognizing even number of 0's and odd number of 1's
I have an assignment, it's asked to write a context free grammar recognising the language $L=\{ w \mid w\text{ has an even number of }0\text{s and an odd number of }1\text{s}\}$, over the alphabet $\{...
1
vote
1answer
81 views
Looking for a formal grammar for $\{ a^{2^n} \mid n \in N\}$
The title says it all. The language $\{ a^{2^n} \mid n \in N\}$ looks quite simple. Yet I could not find a grammar that generates this language.
0
votes
1answer
49 views
Does a pushdown automata exists for the following language?
I have came across a question stating that language $L = a^n b^n c^{2n}$ is not a context free language and hence, no PDA can be constructed for it. But what I am wondering is that, if I add another ...
2
votes
2answers
129 views
Is DFA and Regular Expression equivalent?
The language of a DFA can be the empty set (by defining no final states), but can a Regular Expression do that?
If Regular Expression cannot do that, does it mean that DFA and Regular Expression are ...
1
vote
1answer
41 views
Using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant?
I would like to get some opinions about using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant skills.
When developing these skills one has to provide a large ...
0
votes
1answer
18 views
Question about non recursively enumerable language [duplicate]
Is every language (including languages over alphabet having infinite symbols) which is not recursively enumerable, uncountable?
In other words, let $R$ be the set of languages (including languages ...
3
votes
1answer
47 views
How to prove that a string is made up of subsequences occurring some arbitrary number of times using concatenation?
How to prove that a string, s is made up of n > 1 subsequences occurring some arbitrary number of times using concatenation ...
5
votes
1answer
68 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 ...
4
votes
1answer
57 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
48 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
47 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
55 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
30 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
50 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
12 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
255 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
37 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.
