Tagged Questions

Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

0
votes
1answer
91 views

Decidability of a language of Turing Machine descriptions [duplicate]

Given the language $\{ <M> \mid\:$ M is a Turing machine and there is some w ∈ Σ* for which the computation M(w) takes more than 10 transitions$\}$ How can one prove that this ...
3
votes
1answer
109 views

Why does this pumping lemma application “prove” that 0*1* is not regular?

Here is a proof that $0^*1^*$ is not regular, even though it is regular. I'm having a hard time figuring out what is wrong with the proof. Assume $0^*1^*$ is regular. Let $p$ be the pumping length as ...
1
vote
1answer
116 views

Can $\{a^mb^nc^n\mid m,n \ge 1\}$ be proved non-regular using the pumping lemma?

$\{a^mb^nc^n\mid m,n \ge 1\}$ intuitively seems like a non-regular language. It looks like the machine needs to remember the number of $b$s (which isn't limited). The pumping lemma can be used to ...
0
votes
1answer
56 views

DFA for every run of a's=2 or 3

I am trying to create a dfa for L={w: every run of a's has length either two or three} this is my attempt at the solution..i feel like I am missing something..?
0
votes
1answer
37 views

Find strings in L^4

Let L = {ab,aa,baa}. I need to find L^4. From my understanding, I union the set. So: ...
8
votes
3answers
868 views

Union of regular languages that is not regular

I've come across that question : "Give examples of two regular languages which their union doesn't output a regular language. " This is pretty shocking to me because I believe that regular languages ...
0
votes
2answers
85 views

What does it mean to prove that a set of binary integers is regular?

I'm not exactly sure what this question is asking me to do: Show that the set of binary integers (given as strings over $\{0, 1\}$) that are divisible by $3$ is regular, by giving a DFA that ...
2
votes
2answers
90 views

Prove that REG is closed against removing all but lexicographicaly largest words (per length)

Let $\Sigma_n = \{0, 1, ... , n-1\}$. Suppose $L \subseteq$ $\Sigma^*_n$, and let $\qquad\displaystyle\mathcal{B}(L) = \{ x \in L : x = \textrm{lex}\max L_m, m \in \mathbb{N}_0 \}$, ...
0
votes
2answers
67 views

Does the complement of sigma Kleene star exist?

If $\Sigma^*$ is the set of ALL strings including the empty string, then what can its complement possibly be? The empty set?
1
vote
1answer
85 views

Grammar for ${a^n b^n c^{n+m}}$

Can we define a grammar for the following language? $$L = \{a^n b^n c^{n+m} | n,m>=0\}\,. $$ I can define one for this: $$L=\{a^nb^n|n,m>=0\} $$ S --> aSb | λ or this one: ...
2
votes
0answers
32 views

Tree Languages are Word Languages on an Infinite Alphabet of Contexts

I have been reading the book Tata (Tree Automata Techniques and Applications), and there is a sentence I have read thousands of times, yet still don't quite understand. In the beginning of Chapter 2, ...
4
votes
0answers
34 views

Languages recognized by finite state automata of polynomially growing size

In the course of my research (condensed matter physics stuff), I stumbled over the following concept: The class of regular languages can be defined via finite state machines (FSM): A language $L$ ...
0
votes
2answers
36 views

help understanding formal grammar for subtraction example

I am going through the following document trying to understand a simple grammar for a basic subtraction example (page 4). The example states that Simple arithmetic expressions of arbitrary length ...
1
vote
0answers
16 views

examples of strings that is not in the set [closed]

I'm kind of struggling with finding a string that is not in this set {w: for some u ∈ Σ*, www = uu} where Σ = {a,b} from what I understand, the set of Σ* is, {E, a, b,aa, ab, ba, bb, aaa, ...} if w ...
2
votes
1answer
100 views

Prove that the language is not regular without using Pumping Lemma

I am practising problems on Regular Languages and I came across this question: Prove that the language $$\{a^m b^n : m ≥ 0, n ≥ 0, m \ne n\}$$ is not regular. (Using the pumping lemma for this ...
0
votes
2answers
63 views

Creating a grammar from the language

L = { a^n b^2n a^(n+2) : n>=1 } So I'm trying to construct the grammar and I'm getting stuck.Some example strings would be these (spaced out to help demonstrate the patterns): a bb aaa aa bbbb aaaa ...
0
votes
1answer
37 views

NFA state complexity for the complement of EPAL restricted to a fixed length

I've been having trouble proving the next statement: Let $L_n=\{ww, |w|=n\}$ (the set of equal-length palindromes (EPAL) restricted to length $2n$). Prove that $L^c_n$ can be accepted by an NFA ...
-2
votes
1answer
35 views

Prove that $(L^*M^*)^* = (L\cup M)^*$

I would like to find out how to prove this statement. Thank you. Well I think that I proved one part of the statement, but my proof doesn't really look elegant. My proof of $(L\cup M)^* \subset ...
9
votes
1answer
252 views

Constructing all context-free languages from a set of base languages and closure properties?

One way of looking at regular expressions is as a constructive proof of the following fact: it's possible to construct the regular languages by starting with a small set of languages and combining ...
1
vote
1answer
65 views

Don't understand closure under string reversal

I am trying to learn from http://www.cs.uiuc.edu/class/su08/cs273/lectures/lect_06.pdf #2 and I understand everything except for the 2nd line of delta prime prime function, I having breaking down ...
4
votes
2answers
92 views

Kleene closure of the empty set

In the book introduction to automata theory and languages, $L^*$ is defined as $$L^* = \bigcup_{i=0}^\infty L^i $$ The book also says that $\emptyset^* = \{ \epsilon \}$. But since $\emptyset$ ...
0
votes
1answer
72 views

For two regular languages, why is the set of words from one that don't have a subsequence in the other also regular?

In general, a string $x$ is a subsequence of $w = w_1\dots w_n$ if there are integers $i_1<\dots< i_k$ such that $x = w_{i_1}\dots w_{i_k}$. The subsequence is proper if $k < n$ and $k > ...
3
votes
3answers
177 views

Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language

I was wondering about its proof. The direct use of pumping lemma here is not a viability. So a certain teacher of mine proved this with the notion that $a^{n}b^{n}$ being a subset of this language ...
0
votes
2answers
106 views

Can languages with infinite strings be recursively enumerable?

I am not 100% sure about the definition of recursively enumarable languages. Yes I know how are they defined: There has to exist a Turing machine that accepts all wrods of the language and halts but ...
0
votes
1answer
71 views

Show that the regular languages are closed against taking “the second half” [duplicate]

Given $L$ is regular, the proof that $\mathrm{HALF}(L)$ is regular is pretty straightforward to me (e.g., #11 in this link): simply making a NFA and meeting in the middle with 2 original DFAs, the ...
2
votes
2answers
34 views

Method for measuring the 'similarity' between FSA grammars?

I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic ...
1
vote
2answers
80 views

Proving Regularity of Languages that are 1/k of an already known regular language

There is this question in Kozen, that states if a language is regular then the first half would also be regular. Also I found a material on the internet that extends the thinking saying a language ...
1
vote
1answer
97 views

Unambiguous CFG for $a^ib^j$ where $i \le j \le 2i$

could you please help me for finding an unambiguous CFG for the following expression: $a^ib^j$ where $i \le j \le 2i$
-3
votes
1answer
118 views

Pushdown Automata Challenge

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...
1
vote
1answer
47 views

Context Free or Context Sensitive and why

I was given two languages $$L_1=\{0^k1^k0^m\mid k,m \in \mathbb{N}\text{ and }k < m\}$$ and $$L_2=\{a^mb^{m+1}\}$$ and I was asked to prove whether they are context free or sensitive. For ...
-1
votes
1answer
31 views

Do NFAs with ϵ-transitions accept languages that no PDA can?

Is it correct to say that there are languages that a NFA with epsilon recognizes but a PDA is not? I think that it is wrong but I cannot find a suitable explanation.
3
votes
1answer
78 views

Find a regular language that becomes non-regular if you cut away the middle third of all words

Let $A$ be a regular language, let $A'=\{xz\}$ such that for some $y,|x|=|y|=|z|$ and $xyz\in A$. Show that $A'$ is not necessarily regular language. This is an excercise of Sipser, I've no idea how ...
0
votes
2answers
56 views

Are constituency grammars and dependency grammars two different types of context free grammars?

From http://en.wikipedia.org/wiki/Parse_tree A concrete syntax tree or parse tree or parsing tree[1] or derivation tree is an ordered, rooted tree that represents the syntactic structure of a ...
0
votes
2answers
51 views

Show that the language of words with even sum of positions of a letter is regular

Let $\Sigma=\{a,b\}$, and let $S(a)$ be sum of the positions of $a$ of string $S$. I want to prove $$L=\{S\in \Sigma^{*} \mid S(a)=0(\bmod 2)\}$$ is regular. What I was thinking is to do somehow keep ...
1
vote
0answers
38 views

What is regular about regular languages? [duplicate]

I am new to automata theory. I am well aware of the definition of regular language in automata, that is "a language is called a regular language if some finite automaton recognizes/accepts it" [MS]. ...
-2
votes
1answer
136 views

Why is the language of even-length non-palindromes context-free?

We know $L_1=\{w_1 w_2 \in (a+b)^*\mid |w_1|=|w_2|, w_2 \neq w_1^{\;\mathrm{R}}\}$ is a context-free language. Can anyone help me produce a PDA or give me any hint how I can quickly understand why ...
-3
votes
1answer
64 views

Language of a grammar

What's the language of following grammar? $G: S \to S_1B$ $S_1 \to aS_1b$ $bB \to bbbB$ $aS_1b \to aa$ $B \to \lambda$ any hint or solution?
0
votes
1answer
157 views

What could 'two characters are terminals' mean?

In the context of this statement, what does 'a & b are terminals' mean? Stacks and queues can be used for determining whether a particular input string is in the language or not. L = ...
1
vote
2answers
54 views

Is string matching and replacement considered in formal languages?

Is string matching and replacement, as an operation on strings or on formal languages, considered in formal languages? For example, the family of regular languages, or the family of context free ...
1
vote
1answer
53 views

Expressive power of lexer + parser

Most modern compilers split their syntax analysis into a lexical phase that is followed by a parsing phase. The lexical phase is given by a regular expression, while parsing is guided by a ...
1
vote
1answer
81 views

Non Deterministic PDA accepted language not clear

This is a PDA from the lecture slides I'm using: They say it accepts all words that contain double a's. While it makes some sense it's not full proof. What prevents the second a to be read in the ...
1
vote
3answers
105 views

Unable to understand an inequality in an application of the pumping lemma for context-free languages

The problem Prove that the language $\qquad L = \{a^n b^j \mid n = j^2\}$ is not context free using pumping lemma. Approach taken by the book To prove such statements, the book takes the ...
1
vote
1answer
51 views

Are all Chomsky-Type3 grammars LL(1)?

Referring to this Question, where an answer is stating that all Type 3 languages are LL(1), I'd like to know if all Type 3 grammars are possibly LL(1). If not, why is it so? Are there maybe ambiguous ...
-2
votes
1answer
45 views

Generative grammars and analytic grammars?

What are a generative grammar and an analytic grammar? How are they different from a formal grammar? Is the recursive definition of the language of a propositional calculus, a first order logic ...
-2
votes
1answer
111 views

Is a language closed under string concatenation, repetition, and/or taking substring regular?

Is a language $L$ regular, context-free, context-sensitive, recursively enumerable, or ..., if $L$ is closed under string concatenation, and/or string repetition, and/or taking substring? ...
0
votes
1answer
55 views

Can the definition of regular languages be simplified?

Wikipedia says The collection of regular languages over an alphabet Σ is defined recursively as follows: The empty language Ø is a regular language. For each a ∈ Σ (a belongs to Σ), ...
4
votes
2answers
172 views

Counting the number of words accepted by an acyclic NFA

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. Can we compute $|L(M)|$ in polynomial time? If not, can we approximate it? Note that the number of words is not the same as the ...
7
votes
1answer
82 views

Smallest NFA accepting concatenations of two words of the length $k$ which are different at all positions

Let $k\in \mathbb N$ I'm looking for a small NFA build for the language of concatenation of two words of the length $k$ which are index-wise different, i.e. $$L_k=\{u\cdot v \in \Sigma^* : ...
3
votes
3answers
423 views

Does a logical system have semantics?

From Wikipedia: A logical system or, for short, logic, is a formal system together with a form of semantics, usually in the form of model-theoretic interpretation, which assigns truth values to ...
1
vote
2answers
164 views

What are the definitions of syntax and semantics?

For a formal language $L \subseteq \Sigma^*$ over an alphabet $\Sigma$. From https://proofwiki.org/wiki/Definition:Syntax The syntax of a formal language is its structure, and is specified by a ...