Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

0
votes
1answer
50 views

Using the pumping lemma for a proof by contradiction [duplicate]

I'm trying to prove that the set of even-length strings with the two middle symbols being equal cannot be accepted by finite automata. I can explain why it cannot be accepted intuitively, but I'm ...
1
vote
1answer
23 views

In reference to the Chomsky hierarchy (and automatas), Which is the linear feedback shift register Languages/automaton?

The Chomsky hierarchy is a guideline on language expressive power. The linear feedback shift register is a very interesting "element" to structure a language and there is a large theoretical ...
0
votes
1answer
53 views

Pumping lemma on {a^n | n=3^k} — help finishing the proof [duplicate]

I am working on a pumping lemma question and trying to prove that the following is not regular, but I can't finish the proof, if someone can help me it will be great. So I am given this language: $L ...
2
votes
3answers
87 views

Language Recognition Devices and Language Generators

I have few CS textbooks with me which discuss languages, well actually 2 plus old course notes supplied a few years ago. I have been searching the web too any only seem to come up with vague responses ...
-3
votes
4answers
55 views

Concatenation of regular languages [closed]

Suppose we have two language L = {0^n|n>=0} M = {1^n|n>=0} We know both of these are regular languages. Will L.M (concatenation) be a regular language? ...
9
votes
1answer
120 views

How fast can we decide whether a given DFA is minimal?

Minimizing deterministic finite automata (DFAs) is a problem that has been thoroughly studied in the literature, and several algorithms have been proposed to solve the following problem: Given a DFA ...
2
votes
0answers
55 views

Prove Single-Tape and Non-write Turing Machine can Only Recognize Regular Language?

Here is the problem: Prove the single-tape TM that cannot write on the portion of the tape containing the input string recognize only regular language. My idea is to prove that this particular TM ...
1
vote
1answer
55 views

Definition of “infix” in formal languages

I've got a simple question: Let's say we have the following definition of a language over some alphabet: $L = \{w \mid w \text{ contains the infix } aab\}$ Does that mean $aab \in L$? or does ...
2
votes
1answer
87 views

showing that the pair of Finite Automata are equivalent

Here I am trying to show that the pair of Finite Automata are equivalent. I have tried something but I am not sure if I am in the right direction. This is what I have. These are pairs of FA's. Set ...
0
votes
2answers
80 views

A flawed theorem about regular languages

I am struggling with this question for a very long time and just can't find the flaw. So I am given a false Theorem: The language ${awwa \mid w \in {a,b}^* }% is regular. Well, that part is ...
2
votes
0answers
38 views

What kind of structural features of strings can be described by regular grammars?

Context-free grammars, as well as other types of grammars, can naturally associate structure with the strings of the defined language, for example tree structures in the case of context-free language. ...
0
votes
1answer
43 views

Palindromes and linear grammars

Given a linear grammar G, is it possible to determine if L(G) contains a palindrome?
10
votes
4answers
500 views

Regular language not accepted by DFA having at most three states

Describe a regular language that cannot be accepted by any DFA that has only three states. I'm not really sure where to start on this and was wondering if someone could give me some tips or ...
2
votes
1answer
41 views

CFL not closed under intersection while Turing Decidable are

It makes me wonder that despite of (CFL) being a subset of Turing Decidable languages, Turing Decidable is closed under intersection while CFL is not. Does not Turing Decidable engulf all CFLs?
3
votes
1answer
163 views

Kleene star of an infinite unary language always yields a regular language

Let $L = \{a^n \mid n \ge 0\}$, where $a^0 = \epsilon$ and $a^n = a^{n-1}a$ for all $n \ge 1$. Thus $L$ consists of sequences of $a$ of all lengths, including a sequence of length $0$. Let $L_2$ be ...
-1
votes
2answers
95 views

Prove that languages which contain words whose lengths are multiples of a constant are regular

This is a problem involving the theory of regular languages. I am stuck on this problem and do not know how to solve this type of problem. Prove that the language $B_n = \{ a^k \mid k \text{ is ...
-1
votes
1answer
36 views

Left Linear Grammar: How to construct?

I need help constructing a Left Linear grammar for the language $L = \{ a^n b^m c^p \mid n\geq 2, m\geq 3, p\geq 4 \}$ Here is what I have so far, I know : $N = \{S\}$ $T = \{ a, b, c \}$ $P = ...
3
votes
2answers
72 views

Complexity of CFG grammar for a regular language

I know that each regular language can be generated by a CFG. This makes, in one sense at least: context-free languages more general than regular languages. Are there known results about the ...
1
vote
2answers
109 views

Do Kleene star and complement commute?

I am having hard time solving the following problem. Are there any languages for which $$ \overline{L^*} = (\overline{L})^* $$ Assuming $\emptyset^* = \emptyset$, if I consider $\Sigma = ...
1
vote
1answer
61 views

Are there regular languages between every two non-regular languages?

I have a question regarding regular languages. Given that $L_1$ and $L_2$ are non-regular languages, can a regular language $L$ exist so it is a subset of $L_2$ and $L_1$ subset of $L$? To be more ...
1
vote
1answer
40 views

How do I use the Myhill-Nerode theorem to show that a language is not regular?

My language is the repetition of 0 to a length that's a power of 2: $L = \{ 0^k \mid k=2^n, n \geq 1 \}$ I want to know how to use the Myhill-Nerode theorem to show that this language is not ...
0
votes
0answers
68 views

Proving a regular expression is correct [duplicate]

I'm working on homework for my formal languages and automata course. The text we are using is the first edition of Hopcroft and Ullman (1979). Specifically, I'm unsure how to justify that my regular ...
1
vote
1answer
79 views

Can reversing the final and non-final states of a DFA produce the complement of the original language?

Is this true? If I change all final states of a given Deterministic Finite Automata to non final states and all non final states to final states then does this new automata represent the complement of ...
0
votes
1answer
64 views

Is this grammar LL(1)?

Consider following grammar: $$X\to Yc|ZY$$ $$Y\to ab|cX$$ $$Z\to d|\epsilon$$ Can this be converted to LL(1)? Cleary, its not LL(1) because of First/First conflict at first production. Can anyone ...
5
votes
1answer
77 views

How to find a Deterministic PDA for an intersection of languages

There are two languages, $\qquad L_1 = \{w\in\{a,b\}^*: N_a\leq N_b\}$ and $\qquad L_2=\{w\in\{a,b\}^*: N_b\leq 2N_a\}$ where $N_a$ means the number of occurrences of $a$ in the string $w$. Same ...
1
vote
1answer
74 views

Proving that {0^{2^k}} is not regular with the Myhill-Nerode theorem [duplicate]

My language is the repetition of 0 to a length that's a power of 2: $L = \{ 0^k \ni k=2^n, n \geq 1 \}$ I want to know how to prove that this language is not regular. I have attempted the proof ...
1
vote
3answers
72 views

How can both |y| = 0 and y⁰ = ε hold in the Pumping lemma?

There is something in the pumping lemma that I do not quite understand, namely if $s$ is at least of length $p$, then we could split it to $xyz$ such that the following conditions are met: For each ...
0
votes
2answers
78 views

Is $a^{n+m}b^{n}c^{m}$ context free?

Language: $ L = a^{n+m}b^{n}c^{m} $ As per a recent test I gave, this language is not context free. However, I think it is. Corresponding Grammar: $ X \rightarrow aXY \space |\space \epsilon $ $ ...
1
vote
3answers
44 views

Precedence in regular expressions

I'm having trouble finding the language represented by the following: (AA|BB)* Should the expression be read as... ( A (A|B) B ) * or... ( (AA) | (BB) )* If that isn't clear, should this produce ...
4
votes
2answers
796 views

Difference between 1* + 0* and (1 + 0)*

I know that (1 + 0)* is the set of all bit strings; but isn't 1* + 0* the same thing?
0
votes
0answers
39 views

Find the language generated by a grammar

I have to find the language generated by the grammar: $\qquad\begin{align*} S &\to SA \mid a \\ A &\to aAa \mid bA \mid \varepsilon \end{align*}$ where $\varepsilon$ is the empty ...
4
votes
1answer
65 views

Glue-concatenation v.s concatenation

I wanted to give the following as a homework question, but my first few attempts to solve it failed, so now I'm just curios for a solution: For two words $x,y\in \Sigma^*$ and for a letter $\sigma\in ...
0
votes
0answers
13 views

Unambiguous Context free Grammar [duplicate]

I was reading through Context Free Grammar, and I came across ambiguous grammar. If the language produced by CFG has more then 1 parse tree, then CFG is an ambiguous grammar. Is there any way by which ...
0
votes
0answers
46 views

Is the language of words with as many a's in the first as b's in the second part context-free?

Is $L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? Can we construct an NPDA for the language? There is a book here that claims $L$ is not CF (without any elaboration), ...
1
vote
2answers
148 views

Closure of CFL against right-quotient with regular languages

Let $A/B$ = $\{ w \mid wx \in A$ for some $x \in B \}$. Show that if A is context free and B is regular, then $A/B$ is context free. My interpretation of this is is that we need to show that if ...
0
votes
2answers
79 views

Regular language concatenation with superset

Let $A$ be some alphabet. $A$ itself is a regular language. $E = A^*$ is regular language over $A$. $E$ is a superset of all languages over $A$, regular or otherwise, i.e $E$ contains every possible ...
2
votes
1answer
71 views

Is this the correct way to use the pumping lemma?

I've been watching lectures from Coderisland on YouTube about finite state machines, DFAs and NFAs, and in one discussion he talks about how to use the pumping lemma to show how a language is not ...
0
votes
0answers
44 views

Is this a grammar for arithmetic expressions?

Describe the language generated by the following grammar <A> ::= <A><A> '+' | <A><A> '*' | 'a' So it's not too hard to see ...
3
votes
1answer
72 views

NFA to DFA final states proof

When translating an NFA into an equivalent DFA, we can say that all states that contain the final states of NFA, is the final state of DFA. What should my arguments be in order to prove this? ...
1
vote
1answer
60 views

Kleene star closure of a context free grammar

I have this question about closure of a context free grammar, and if someone can check my answer and see if it makes sense, and if not, what is missing, I would be very grateful. Give an ...
0
votes
1answer
30 views

$L \in RE/R$ such that $L^R \cup L \in R$

Prove/disprove: $\exists L \in RE/R$ such that $L^R \cup L \in R$ Where in my context, $R$ is the turing decidable, and $RE$ is the recursively enurmable. I tried to find such an $L$ but ...
6
votes
1answer
164 views

Why is ww a linear indexed language while www is not?

I am a little bit confused on one idea regarding indexed languages. $\{ww \mid w \in \{a,b,c\}^* \}$ is a linear indexed language, but $\{www \mid w \in \{a,b,c\}^* \}$ is not a linear ...
3
votes
2answers
158 views

How to get 2-state PDA for CFG?

I'm studying for my Computing languages test and there's one idea I'm having problems wrapping my head around, as far as I know for any Context Free Grammar (CFG), we can design a 2-state Pushdown ...
1
vote
1answer
96 views

Proof that {$a^m b^n$ | m!=n} is not regular [duplicate]

I know that the language $\{a^m b^n | n\neq m\}$ satisfies the pumping lemma, but it's still not regular (I have to count the # of a's and b's). How can I formally prove it?
3
votes
1answer
41 views

If L is a non-regular language over {a}, are all Myhill-Nerode classes singletons?

Is there a non-regular language over unary alphabet $\{a\}$ which has a Myhill-Nerode equivalence class that is not a singleton?
3
votes
1answer
100 views

If $L$ is CFL and $\overline{L}$ is CFL, then is L regular?

I've seen in previous exams that professors marked the theory as correct: If $L$ is CFL and $\overline{L}$ is CFL, then L is regular. I just don't see how this would work. How would we prove ...
2
votes
1answer
44 views

Prove that A* is the smallest reflexive and transitive set containing A

I'm trying to learn automata theory on my own and I am running into an issue with the second part of the question: We say B is transitive if $BB\subseteq B$ and reflexive if $\epsilon \in B$ Show ...
0
votes
1answer
92 views

If $L^*$ or $L^+$ is empty, can L be an infinite language?

I have to prove or disprove the implications in these two situations $L^* = \emptyset$ $\rightarrow$ $L$ is infinite $L^+ = \emptyset$ $\rightarrow$ $L$ is infinite Here are my thoughts. I would ...
0
votes
1answer
18 views

Decidability of fullness of intersection of a CSL with a regular language

Let $L_r$ be a regular language with alphabet $\Sigma$ and $L_{\text{csl}}$ be a context sensitive language. Are any of the following questions decidable? $L_r \cap L_\text{csl} \stackrel{?}{=} L_r$ ...
1
vote
1answer
46 views

Is the following language context-free? $L= \{a^nb^m| m\geq2^n\}$

Is $L=\{a^nb^m|m\geq2^n\}$ a context-free language?