Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

learn more… | top users | synonyms

0
votes
1answer
29 views

Prove about $NFA$ and pumping lemma

The question: Let it be $L$ a regular language. few definitions: $p(L)$-the minimum natural number so that $L$ fulfills the pumping lemma. $n(L)$- minimal NFA that accepts $L$. $m(L)$- $Rank(L)$, the ...
0
votes
1answer
21 views

Regular Pumping Lemma

$$\begin{align*} L&=\left\{b^5w:w\in\{a,b\}^*,\big(2n_a(w)+5n_b(w)\big)\bmod 3=0\right\}\\ L&=\left\{(ab)^na^k:n>k,k\ge 0\right\} \end{align*}$$ Determine if each language is regular ...
0
votes
1answer
35 views

which of the following languages are regular?

If w,x,y ∈ (a+b)^+ 1)L=wxwy 2)L=xwyw 3)L=wxyw According to me all of them should be non-regular since we can't actually check what will be the starting symbol of first occurrence of w since it ...
0
votes
1answer
25 views

Prove that relates to pumping lemma that I am not sure about

So, I will define like in my last post (for a regular language $L$): We will define $p(L)$ to be the minimal natural number so that a language $L$ fulfill the pumping lemma. We will also define ...
0
votes
0answers
23 views

How to prove that a simple NFA is minimal, without any algorithm?

First, I will present the question I was doing: We will define $p(L)$ to be the minimal natural number so that a language L fulfill the pumping lemma. We will also define $n(L)$ to be the minimal NFA ...
0
votes
0answers
10 views

what is the relation between CFG , LL(K) ,LR(K) and regular grammars?

I am clear with only the concept that LL(k) grammars are the one which are a subset of context free grammar and are not left-recursive ,and LR grammars are one which are parsed by bottom up parsers ...
0
votes
1answer
14 views

when do we say a grammar to be unambiguous with respect to parse tree and derivation tree?

In normal terminology we say that both the parse and derivation trees are same in meaning so if a grammar derives one string with left derivation as well as right derivation then it is ambiguous , if ...
1
vote
1answer
18 views

Proving this language is non context-free

How can I prove that the language $\{ab^kab^kab^k\subset \{a,b\}^* | k \geq 0\}$ is non context-free? I've tried applying the pumping lemma but can't write a proof without considering multiple ...
0
votes
0answers
23 views

Is the resulting language regular?

If $L$ is a regular language then is $L'=\{w \mid wx \in L \text{ for some string }x\}$ regular? First step is understand $L'$. So it is a subset of $L$ that contains strings with a certain prefix?
0
votes
1answer
96 views

What does arbitrary number mean?

A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits). Is it true ? My attempt : Arbitrary length means variable length, and there ...
0
votes
1answer
23 views

Identify the class of language?

Given a set $$S=\{x∣ \text{there is an x-block of 5's in the decimal expansion of π}\}$$ (Note: x-block is a maximal block of x successive 5's). Identify class of language? Somewhere it ...
0
votes
0answers
69 views

Equivalence class of regular language

let be L1,L2 regular language. 𝑅𝑎𝑛𝑘 is how many Equivalence class. i need to prove or to contradict: RANK(L1∪L2)≤RANK(L1)*RANK(L2) RANK(L1∪L2)≤RANK(L1)+RANK(L2) i think the two of them are ...
0
votes
1answer
33 views

Proving that the language $\mathscr L$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{\text{all the binary words such that the number of ones divide the number of zeros}\}$ is non regular using the pumping lemma For example: ...
0
votes
1answer
18 views

Designing a DFA to accept a string

I have created the following FA Im i correct?
1
vote
0answers
49 views

Is $r(^∗)=r^∗$ valid regular expression?

Which of the following regular expression identities is/are TRUE? $r(^∗)=r^∗$ $(r^∗s^∗)=(r+s)^∗$ $(r+s)^∗=r^∗+s^∗$ $ r^∗s^∗=r^∗+s^∗$ My attempt : I can't say anything, but it should be ...
0
votes
1answer
33 views

Proving that $\mathscr L=\{0^n \big|\text{n is the square of a natural number }\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{0^n \big|\text{n is the square of a natural number}\}$ is non regular using the pumping lemma My try: $\mathscr ...
1
vote
1answer
11 views

Proving that the language $\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma My try: $\{a,b\}^*=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,\dots\}$ ...
0
votes
0answers
14 views

If M1 and M2 are 2 TM’s such that L(M1) = L(M2) , then which of the following conditions are true?

(a) On every input on which M1, doesn’t halt, M2 doesn’t halt. (b) On every i/p on which M1 halts, M2 halts too. (c) On every i/p which M1 accepts, M2 halts. How to approach this question ?
0
votes
0answers
8 views

transitively closed and NFA and DFA states

These are true or false questions given on a quiz. How can I approach these two statements: ( the "e" represents the $\lambda$) to find the correct answer. a. To make the $\lambda$ moves ...
-1
votes
0answers
11 views

Constructing a Minimal DFA from L = (ab + b)* ba using Brzozowski's derivatives method

How would I use Brzozowski's derivatives method to construct a minimal DFA recognizing the language defined by the rational expression: L = (ab + b)* ba
1
vote
1answer
24 views

Checking if Post Correspondence Problem has a Solution

I have the following problem I think that solution is wrong because x1=b and y1=b3(cube).They do not match,So how is this solution possible?
0
votes
0answers
17 views

Conversion of CFG to Chomsky Normal Form

I have the following question I have answer for the first one as S->C1S C1->C2A C2->a S->C2A ...
0
votes
1answer
17 views

Build a DFA that accepts strings over $\{0,1,2\}$ that are divided by $3$ and doesn't include the substring $012$.

I am attempting to Build a DFA that accepts over $\{0,1,2\}$ that are divided by $3$ and doesn't include the substring $012$. What I tried doing is taking the original 3 states of a DFA that accepts ...
2
votes
0answers
19 views

Writing a regular expertion for the language $L=\{0^n1^m|n\equiv m(\mod 2)\}$

I need to write a regular expertion for the language of all the binary words that contains continuum of even number of zeros and after that even number of ones or odd number of zeros and after that ...
0
votes
1answer
11 views

Language of all the binary words that not contains continuum of more then $3$ zeros

I need to write a regular expertion for the language of all the binary words that not contains continuum of more then $3$ zeros, for example $0011110100\in L,\,\,\,\,\,\,\,\,\,11000001100\notin L $ ...
1
vote
1answer
40 views

Design a DFA to check whether the Given Number is Even

I have the following question I have designed the following A Binary String is even if it is ending with 0 and odd if its ending with 1.I have applied this.Im i right ? UPDATE:
0
votes
1answer
24 views

Language of all the binary words that contain $010$ at least twise

I need to write a regular expertion for the language of all the binary words that contain $010$ at leasr twise, note that $101010$ should be accept too because $1\color{blue} {010}10$ and ...
0
votes
0answers
17 views

Minimization of DFA

I have the following question I have minimized the DFA as the following since the states can only be partitioned to [S0][S1 S2] EDIT: Is my Minimization correct?
0
votes
0answers
10 views

Deterministic FSM accepting a binary string whose number of zero is either multiple of 2, 3, or both

I can build a FSM that accept binary string with multiple of 2 number of 0, and I can also build a FSM that accept binary string with multiple of 3 number of 0, but I cannot figure out how I can ...
0
votes
2answers
32 views

Using the Pumping Lemma to show that the language of all strings of even length having no $0s$ in their second half is not regular

I'm struggling with finding a starting string $s$ to prove using the Pumping Lemma that language $$L = \{w \mid w\text{ has even length and the second half of $w$ does not contain any $0$s}\}$$ is ...
0
votes
0answers
17 views

Finite automata dfa/nfa language problem review

I have completed the questions below but am not sure if they are correct. If anyone could help me confirm them it would be much appreciated. 3) This took me a little while but it seems to hold up. Im ...
0
votes
0answers
52 views

Panalphebetic strings provable by DFA?

Is the language of panalphabetic strings decidable by DFA? If so, how can I prove it? A string {a,…,z}* is said to be panalphabetic if it contains at least one occurrence of each letter.
0
votes
1answer
24 views

Pumping lemma for context free. How do I define the string 'w' and define cases?

I am new to the pumping lemma for context free grammars. I have read books and researched online about the pumping lemma, however I am finding it difficult to understand the actual concept and how to ...
0
votes
1answer
14 views

NFA Containing 'a'

I have L={Contains 'a'} and Alphabet(E)={a,b} Can i create a NFA Like this
0
votes
1answer
26 views

Wrong prove for $L=\{a^m:m\geq 0,\; m \mod 3\neq 0\}$ isn't regular, but why?

First, let me just say that this language is regular, and I understand why. But before I understood that, I tried proving that L isn't regular with pumping lemma. I just can't figure what is wrong ...
1
vote
1answer
20 views

Checking if $L_1 \cup L_2$ is regular language

Let $L_1=\{a^n b^r|n \geq 1, r\geq1,n=r\}$ $L_2=\{a^n b^r|n \geq 1, r\geq1,n\neq r\}$ be a non regular languages $L_1 \cup L_2$ is regular? I think that $L_1 \cup L_2$ is regular because we ...
2
votes
1answer
66 views

Let M range over turing machine descriptions .Consider the set REG={M|L(M) is a regular set} which of the statements are true?

The complement of REG is Co-REG REG is recursively enumerable but Co-REG is not REG is not recursively enumerable but Co-REG is Both are recursively enumerable 4.None of them are recursively ...
1
vote
2answers
47 views

How to prove that $L=${$a^p$: p is prime} isn't regular?

I tried using pumping lemma or finding infinite equivalence classes, but I didn't succeed. It's clear to me that there is no automata that accepts this language, but I just can't formally prove that ...
0
votes
1answer
212 views

Prove that $wu=uw$, given that $w^5=u^3$

Suppose $w,u\in\Sigma^*$, $w^5=u^3$, and I need to show that $wu=uw$. I started with $5|w|=3|u|$, but I didn't know how to continue... any suggestions?
0
votes
1answer
42 views

Which of these languages are regular?

Consider the following subsets of $\{ a, b, \$ \} ^*$: $A = \{ xy \mid x,y \in \{ a, b, \} ^*, \#a(x) = \#b(y) \}$ and $B = \{ x \$ y \mid x,y \in \{ a, b, \} ^*, \#a(x) = \#b(y) \}$. Which of the ...
2
votes
3answers
38 views

How can I implement a Deterministic finite automaton which accepts strings having specific words.

I am trying to make a Deterministic finite automaton which accepts those strings having two specific words(either one) anywhere as a substring. The problem is really simple if the characters of the ...
0
votes
1answer
33 views

Writing a Context Free Grammar for a language with multiple strings in the language

I have an interest in computing and want to learn more about the actual theory behind it. Context Free Grammar plays a part and I am quite fascinated by it all. However, I came with a language that ...
0
votes
2answers
30 views

What is the language of following CFG?

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals. $$S → aS \mid A \\ A → aAb \mid bAa \mid \epsilon$$ Which of the following ...
1
vote
1answer
31 views

How we derive language from grammar by bottom up or any other approach?

Consider a CFG with the following productions. S → AA | B A → 0A | A0 | 1 B → 0B00 | 1 $S$ is the start symbol, $A$ and $B$ are non-terminals and $0$ and $1$ are ...
1
vote
1answer
28 views

proving that if a FFA accepts L=> L is a regular language

Ok, so after wasted time for nothing on this question that I asked yesterday: proving that a regular language can be accepted by a fast finite automaton Now comes the more interesting prove: ...
0
votes
0answers
16 views

Removing null moves from automata

I need to bulid the equal auomaton non-deterministic automaton but without the "epsilon moves" ($\lambda $ is epsison in this case) (The double circle is 'Accept') My try: I don't ...
0
votes
1answer
33 views

proving that a regular language can be accepted by a fast finite automaton

Let it be L a regular language. Prove that exists a fast finite automaton (FFA) M which excepts L. Definition of FFA: FFA is a 6-tuple M=$<Q,Σ,P,δ,s,A>$ which: 1. Q is a finite set of ...
4
votes
2answers
47 views

proving that $L_\text{almost}$ is a regular language

Let it be L, a regular language. we will define: $L_\text{almost} = \{ w'\mid \exists w\in L\ w' \text{ is almost similar to }w \}$ a word $w'$ is almost similar to $w$ if they are in the same ...
0
votes
1answer
15 views

If $L_1$ and $L_2$ are non regular then $L_1 \cup\;L_2\; = L$ can be regular?

I need to prove or disprove with contrast example: If $L_1$ and $L_2$ are non regular then $L_1 \cup\;L_2\; = L$ can be regular I have no idea how to begin, hints and spoilers are welcomed
0
votes
1answer
27 views

DCFL are closed under Intersection with Regular Languages?

Let $L_1$ be a regular language, $L_2$ be a deterministic context-free language and $L_3$ a recursively enumerable, but not recursive, language. Which one of the following statements is false? $L_1 ...