Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

2
votes
2answers
33 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$ ...
1
vote
1answer
19 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 ...
2
votes
2answers
22 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
1answer
30 views

If both $L$ and $L_1$ are regular, does it follow that $L \diamond L_1$ is 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 > ...
0
votes
2answers
56 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 ...
2
votes
5answers
2k views

Recursive and recursively enumerable language definition for a layman

I've come across many definitions of recursive and recursively enumerable languages. But I couldn't quite understand what they are . Can some one please tell me what they are in simple words? Thanks ...
0
votes
1answer
31 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 ...
1
vote
2answers
65 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
83 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$
6
votes
1answer
199 views

Can this CFG be written into an equivalent LL(1) grammar?

I have the following CFG which I suspect cannot be rewritten to one which is LL(1): $S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS\ |\ cSdS\ |\ dScS$ I've thought about it for a while, and can't seem to ...
0
votes
0answers
8 views

How to exclude Code snippets from Microsoft Words spell check [migrated]

I am writing on an computer scientific report and I'm really tired of Word 2010 always switching between languages (code in english, text in german) and marking all my code red just because there are ...
-2
votes
0answers
16 views

Prefix closure of the language [duplicate]

If Σ is a finite set of symbols and α is a word in Σ ∗ , then a word β in Σ ∗ is said to be a prefix of α if α = β γ for some γ ∈ Σ ∗ . For example, the prefixes of the word abbab are λ , a , ab , abb ...
0
votes
2answers
39 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 ...
-3
votes
1answer
94 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
38 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 ...
2
votes
4answers
354 views

Context-free grammar for language with unequal numbers of a and b

I've been trying to get a CFG for the language of all words with unequal numbers of a and b, i.e. $$\{u \in \{a, b\}^* \mid \text{number of occurrences of $a$ and $b$ in $u$ are unequal} \},$$ but ...
-1
votes
1answer
26 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
72 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 ...
4
votes
1answer
107 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 ...
-2
votes
0answers
23 views

Given some languages illustrate which is Regular and why other is not? [duplicate]

Are these languages Regular ? How do we determine in such cases whether the language is regular or not ? 1) $$\left\{ xw{ w }^{ R }\quad |\quad w,\quad x\quad \epsilon \quad { \{ 0,1\} }^{ + } ...
0
votes
2answers
48 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
37 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
90 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
61 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
153 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
53 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
50 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
3answers
85 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
58 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
1answer
40 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
83 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? ...
-2
votes
1answer
39 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 ...
0
votes
1answer
52 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 Σ), ...
11
votes
1answer
161 views

The number of different regular languages

My question is: Given an alphabet $\Sigma = \{ a,b \}$, how many different regular languages are there that can be accepted by an $n$-state nondeterministic finite automaton? As an example, let us ...
7
votes
1answer
72 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
421 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
121 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 ...
2
votes
1answer
56 views

Neural network: noisy temporal sequence converter (transducer?producer?) on demand?

I start to suspect this problem is very hard now that I cannot find a single relevant literature on the subject, but it's too late to change the class project topics now, so I hope any pointers to a ...
1
vote
1answer
75 views

What are the meanings of metalanguage and metasyntax and EBNF?

I am trying to understand what BNF, metalanguage, and metasyntax are. From https://proofwiki.org/wiki/Definition:Metalanguage A metalanguage of a formal language is a formal language used to ...
-5
votes
1answer
34 views

What is the language generated by the following grammar? [closed]

Could please tell me the language generated by this grammar? S->iS |iSeS|ε
-2
votes
1answer
49 views

How to write this regular expression

Consider the language over the alphabet $\sum= \{a\}$ containing strings whose length is either a multiple of 2 or 3 (including the empty strings). Writing a regular expression for this language
5
votes
1answer
70 views

Infinite non-regular decompositions of regular languages

The title pretty much says it: I'm interested in examples of infinite families of non-regular, pairwise disjoint languages whose union is regular. When is this the case? Or, from a different ...
0
votes
1answer
70 views

A DFA recognizing my name

How can I know if my DFA is implemented correctly? For example, I need to build a DFA, and then minimize it which will recognize my name. Language which describe my name is: L = {pustai, marius} I ...
2
votes
1answer
30 views

Describing explicitly the MyHill-Nerode classes created by a language

I want to practice proving a language is regular or not using the MyHill-Nerode theorm, but for that I need to be able to describe the classes. Here's my practice attempt: For the language ...
0
votes
1answer
39 views

Is there a PDA for every Type 3 Grammar?

we learned that for every type 2 grammar G exists a PDA A with L(A) = L(G). But does for every type 3 grammar G exist a PDA A_G with L(A_G) = L(G)? I think it does, because type 2 grammar is a subset ...
3
votes
3answers
61 views

generate possible inputs valid for automata

I find lots of solution where you have an Automata and a input string , you can validate whether input string is accepted by automata or not. Can we do the reverse ? I am looking for solution which ...
-3
votes
2answers
79 views

Grammar for a language with 1/3 of a's

I have this language: $$ L = \left\{ w \in \{a,b,c\}^* \;\big|\; |w| / |w|_a = 3 \right\} $$ where $|w|_a$ is the number of occurrences of $a$. How can I find a grammar that generates it?
3
votes
1answer
237 views

How to convert a non-embedding context free grammar to regular grammar?

Please note that I am aware the undecidability of the conversion of context-free grammar to regular grammar. But given the non-embedding property of the input context-free grammar, is there any ...
0
votes
1answer
39 views

CFL, pumping lemma

I have difficulty with proving that the language $ L = \{ a^p b^q | p \ge 1 , q \ge 1 , p \ge q^2 \vee q \ge p^2\}$ $ w = uvxyz $ I've chosen word $ w = a^{N^2} b^N $ where $ N $ is a constant ...
1
vote
3answers
62 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 ...